9
$\begingroup$

This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.

The cycles and complete bipartite graphs are hamiltonian (trivial).

The girth-6 graphs are the incidence graphs of the projective planes. The classical finite-field planes are hamiltonian by Singer, but there are lots of nonclassical planes.

And what about the girth-8 and girth-12 case?

EDIT: Corrected the girth-6 case as pointed out by Gordon Royle.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Singer’s result is about the classical Desarguesian projective plane defined over a finite field. There are huge numbers of non-classical planes, and at first sight I cannot see why they should be Hamiltonian. $\endgroup$
    – Gordon Royle
    Commented Jun 12, 2018 at 10:23
  • $\begingroup$ The collinearity graph, i.e. the distance 2 graph on one part of the bipartition, in the girth 8/12 case is Hamiltonian (at least when the number of vertices is large enough) by the results of Krivelevich and Sudakov (people.math.ethz.ch/~sudakovb/pseudo-hamiltonian.pdf). But I am not sure if this implies Hamiltonicity of the the bipartite graph. May be I am missing something obvious ... $\endgroup$
    – Anurag
    Commented Sep 12, 2018 at 14:32

1 Answer 1

Reset to default
2
$\begingroup$

This recent paper of Sato and Suzuki shows that the graphs corresponding to some classical generalized quadrangles are indeed Hamiltonian:

Sato, H. & Suzuki, H. Graphs and Combinatorics (2018). https://link.springer.com/article/10.1007/s00373-018-1940-6

Improve this answer
$\endgroup$

You must log in to answer this question.

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