zbMATH — the first resource for mathematics

New record graphs in the degree-diameter problem. (English) Zbl 1178.05038
Summary: In 1994, M. J. Dinneen and P. R. Hafner [Networks 24, No. 7, 359–367 (1994; Zbl 0806.05039)] published a table of largest orders of graphs of given degree up to 15 and diameter up to 10, known to that date. The table also contained 48 new values found by the authors with the help of computer searches over Cayley graphs of semidirect products of (mostly) cyclic groups. Prior to our work, only relatively few values in the table have been improved; updates have been maintained on the web.
With the help of voltage graphs in combination with random computer search we have substantially improved more than half of the values in (all earlier updates of) the table.

05C12 Distance in graphs
05C38 Paths and cycles
05C07 Vertex degrees
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)