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.

$\endgroup$
  • 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 Jun 12 '18 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 Sep 12 '18 at 14:32
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.