New results on the degree-diameter problem for undirected graphs

Francesc Comellas

Abstract


This paper presents fourteen newly discovered largest undirected graphs with specified degree and diameter, identified since the publication of the comprehensive survey by M. Miller and J. Širáň (Electron. J. Combin. DS14, 2nd. edition. May 2013). These findings advance the longstanding investigation of the degree-diameter problem, a key topic in graph theory, and offer a fresh insight for both theoretical research and practical applications in network design and combinatorial optimization.


Keywords


large graphs; degree-diameter problem; Cayley graphl

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.14

References

M. Abas, Large networks of diameter two based on Cayley graphs, In: Silhavy, R., Senkerik, R., Kominkova Oplatkova, Z., Prokopova, Z., Silhavy, P. (eds) Cybernetics and Mathematics Applications in Intelligent Systems. CSOC 2017. Advances in Intelligent Systems and Computing, 574, 225–233, Springer, Cham, 2017, doi:10.1007/978-3-319-57264-2_23.

I. Alegre, M.A. Fiol, and J.L.A. Yebra, Some large graphs with given degree and diameter, J. Graph Theory., 10 (1986), 219–224, doi:10.1002/jgt.3190100211.

J. Chen, Personal communication ([email protected]), October 16, 2018.

F. Comellas, Table of Large Degree/Diameter Graphs, Mendeley Data, V7, 2024, doi:10.17632/d75dzbjd4k.

M.J. Dinneen and P.R. Hafner, New results for the degree/diameter problem, Networks., 24 (1994), 359–367, doi:10.1002/net.3230240702.

J. Gómez, Some new large (Δ, 3)-graphs, Networks, 46 (2009), 82–87, doi:10.1002/net.20254.

J. Gómez, M.A. Fiol, and O. Serra, On large (Δ, D)-graphs, Discrete Math., 114 (1993), 219–235, doi:10.1016/0012-365X(93)90368-4.

A.J. Hoffman and R.R. Singleton, On Moore graphs with diameters 2 and 3, I.B.M. Jour., 4 (1960), 497–504, doi:10.1147/rd.45.0497.

E. Loz and J. Širáň, New record graphs in the degree-diameter problem, Australas. J. Combin., 41 (2006), 63–80, https://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p063.pdf.

M. Miller M and J. Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., DS14 (2013), 92, doi:10.37236/35

J.J. Quisquater, Structures d’interconnexion: constructions et applications, Tech. Rep. Thèse d’etat, LRI, Université de Paris Sud, Orsay; LRI, Université de Paris Sud, Orsay, 1987. https://www.sudoc.fr/126364826, Accessed April 22, 2025.

V. Pelekhaty, Personal communication ([email protected]), August 6, 2021.

A. Rodríguez de los Santos, Búsquedas masivas de grafos de gran orden con grado y diámetro acotados, Tesis de maestría, Universidad de la República (Uruguay), Facultad de Ingeniería, 2013, https://www.colibri.udelar.edu.uy/jspui/bitstream/20.500.12008/24170/1/Rod13.pdf, Accessed April 22, 2025.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats