Skip to main content
deleted 141 characters in body
Source Link
Kim Morrison
  • 7.8k
  • 7
  • 48
  • 75

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?

I was going to tag this as Community Wiki, because there might not be a definitive answer, but it seems that is no longer an option.

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?

I was going to tag this as Community Wiki, because there might not be a definitive answer, but it seems that is no longer an option.

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?

Post Made Community Wiki by Kim Morrison
Source Link
Robin Saunders
  • 3.6k
  • 24
  • 34

Generalized Moore Graphs

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?

I was going to tag this as Community Wiki, because there might not be a definitive answer, but it seems that is no longer an option.