Smallest Regular Graphs of Given Degree and Diameter
Martin Knor
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 187-191 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267745 
@article{bwmeta1.element.doi-10_7151_dmgt_1702,
     author = {Martin Knor},
     title = {Smallest Regular Graphs of Given Degree and Diameter},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {187-191},
     zbl = {1285.05101},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1702}
}

Martin Knor. Smallest Regular Graphs of Given Degree and Diameter. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 187-191. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1702/

[1] E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo Univ. 20 (1973) 191-208. | Zbl 0275.05121

[2] E. Bannai and T. Ito, Regular graphs with excess one, Discrete Math. 37 (1981) 147-158. doi:10.1016/0012-365X(81)90215-6[Crossref]

[3] R.M. Damerell, On Moore graphs, Proc. Cambridge Philos. Soc. 74 (1973) 227-236. doi:10.1017/S0305004100048015[Crossref] | Zbl 0262.05132

[4] P. Erdös, S. Fajtlowicz and A.J. Hoffman, Maximum degree in graphs of diameter 2, Networks 10 (1980) 87-90. doi:10.1002/net.3230100109 | Zbl 0427.05042

[5] A.J. Hoffman and R.R. Singleton, On Moore graphs with diameter 2 and 3, IBM J. Res. Develop. 4 (1960) 497-504. doi:10.1147/rd.45.0497[Crossref] | Zbl 0096.38102

[6] M. Knor and J. Širáň, Smallest vertex-transitive graphs of given degree and diameter, J. Graph Theory, (to appear).[WoS] | Zbl 1280.05066

[7] M. Miller and J. Širáň, Moore graphs and beyond: A survey of the degree-diameter problem, Electron. J. Combin., Dynamic survey No. D14 (2005), 61pp. | Zbl 1079.05043