5
$\begingroup$

Are there known families of distance-regular graphs with girth larger than 4 where for given vertex/edge count there are more than one non-isomorphic instances? The following is what I have found so far (but none of them satisfies the criteria):

  • Hadamard graphs (non-isomorphic instances exist for $n \geq 64$ but girth is 4)
  • Strongly regular graphs (non-isomorphic instances exist for $n \geq 16$ but girth is 3 for $\lambda > 0$)
  • Others such as cycles and odd graphs have arbitrarily large girth but they do not have more than one non-isomorphic instance for given vertex/edge count.

Is this a known open problem? Thanks in advance for any pointers.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

The point-line incidence graph of a finite projective plane is distance regular with diameter three and girth six. In fact a bipartite graph with diameter three and girth six is necessarily the incidence graph of a projective plane. Next, the point-line incidence graph of a generalized quadrangle with parameters $(s,s)$ is distance regular with diameter four and girth eight. In both cases the parameters of the geometry determine the parameters of the graph, and the geometries are isomorphic if and only if the graphs are.

If $n$ is a prime power but not a prime and $n \ge9$, there are at least two projective planes of order $n$. For the generalized quadrangles we have the $W(q)$ ones, constructed from a symplectic space of dimension four over $GF(q)$, with parameters $(q,q)$. There is a second family of GQ's with these parameters constructed from ovals in projective planes, but to get get non-isomorphic graphs we need non-isomorphic ovals which means we must work in characteristic two.

If you'll forgive a self-reference, the graphs corresponding to the classical projective planes and the graphs belong to whiat I've called the $W(q)$ GQ's are described in detail in my book with Royle.

The standard source of info for distance-regular graphs is the book by Brouwer, Cohen and Neumaier (titled "Distance-Regular Graphs"). The standard for GQ's is by Payne and Thas (titled "Generalized Quadrangles", seems to be online at http://cage.ugent.be/~bamberg/FGQ.pdf).

Both these families are examples of "generalized polygons", but knowing this might not help much.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Chris, thanks for the examples and the pointers. This is exactly what I was looking for. $\endgroup$
    – Francis C
    Commented Dec 30, 2011 at 2:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .