Abstract | ||
---|---|---|
The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.dam.2012.02.023 | Discrete Applied Mathematics |
Keywords | Field | DocType |
various relaxation,specified degree,moore graph constraint,radial moore graph,existence question,new case,maximum number,moore graph,de bruijn graph,radius | Discrete mathematics,Odd graph,Indifference graph,Combinatorics,Strongly regular graph,Moore graph,Chordal graph,Pathwidth,1-planar graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
160 | 10-11 | 0166-218X |
Citations | PageRank | References |
3 | 0.51 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Geoffrey Exoo | 1 | 187 | 39.86 |
Joan Gimbert | 2 | 46 | 6.62 |
Nacho López | 3 | 43 | 9.42 |
José Gómez | 4 | 9 | 2.78 |