3
$\begingroup$

A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore graphs, but are considerably more plentiful (though still quite rare - it has been conjectured that there are finitely many).

The cubic generalized Moore graphs with D ≤ 4 have been known for about 30 years. There are over a hundred of them, mostly of order 30 or 32: they include the G-cages for G ≤ 8, and solutions to the degree-diameter problem for D ≤ 4 (with the case D = 4 having order 38).

However, a preliminary search for literature found very little about the case D ≥ 5. There are no cubic generalized Moore graphs of order 38 < n < 60, because the 9-cages have order 58 and all of them have girth 6. There are (at least) two of order 60, and one of order 70, the latter being again a candidate solution to the degree-diameter problem. There's also one of order 126, the Tutte 12-cage. The only relatively recent paper I was able to find was "Vertex-symmetric generalized Moore graphs" by Sampels, in Discrete Applied Mathematics (2004), which looks at Cayley graphs and doesn't seem to add much that wasn't already known.

I don't know much about this area, but these graphs seem both interesting and relatively easy to construct. Given, if nothing else, the advances in computer hardware over the last few decades, I'm surprised there isn't more prominent literature about them. Do they maybe go by a different name these days? Are there some big results (or at least a more complete census) that I've missed? Are people just not that interested in them, for whatever reason?

$\endgroup$

2 Answers 2

3
$\begingroup$

You are right that there is very little published on the subject.

There are 6 cubic GMGs of order 60 and none of order 62 or 64. This is known from a computational study I did with Catherine Menon that is long overdue for publication (my fault). Order 66 is too hard to do exhaustively by our method. We also have some results for higher degree.

As far as I know (unless I forgot; always possible), it is still not known whether there are cubic GMGs of arbitrarily high diameter.

ADDED: The method is derived from the one used for finding cages in this paper. The modification tries to remove parts of the search that will lead to a too-high diameter, but this is not easy to do. For n=60,62,64 vertices it took 23, 867 and 37600 hours, so the next one might take a century or two.

$\endgroup$
1
  • $\begingroup$ Thanks. Can you give any details about the search algorithm you used, or is that still "under embargo" until you publish? Specifically, I'm interested in (1) whether there are any speedups beyond what's been known for decades, and (2) how long ago your study was - could we get better results with today's computers? $\endgroup$ Oct 17, 2013 at 17:25
2
$\begingroup$

A generalized 2d-gon has girth 2d and diameter d. There are infinitely many examples with d=6 and with d=8.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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