Smallest Regular Graphs of Given Degree and Diameter

Martin Knor

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 1, page 187-191
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Martin Knor. "Smallest Regular Graphs of Given Degree and Diameter." Discussiones Mathematicae Graph Theory 34.1 (2014): 187-191. <http://eudml.org/doc/267745>.

@article{MartinKnor2014,
abstract = {In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.},
author = {Martin Knor},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {regular graph; degree/diameter problem; extremal graph},
language = {eng},
number = {1},
pages = {187-191},
title = {Smallest Regular Graphs of Given Degree and Diameter},
url = {http://eudml.org/doc/267745},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Martin Knor
TI - Smallest Regular Graphs of Given Degree and Diameter
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 187
EP - 191
AB - In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.
LA - eng
KW - regular graph; degree/diameter problem; extremal graph
UR - http://eudml.org/doc/267745
ER -

References

top
  1. [1] E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo Univ. 20 (1973) 191-208. Zbl0275.05121
  2. [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. [3] R.M. Damerell, On Moore graphs, Proc. Cambridge Philos. Soc. 74 (1973) 227-236. doi:10.1017/S0305004100048015[Crossref] Zbl0262.05132
  4. [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 Zbl0427.05042
  5. [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] Zbl0096.38102
  6. [6] M. Knor and J. Širáň, Smallest vertex-transitive graphs of given degree and diameter, J. Graph Theory, (to appear).[WoS] Zbl1280.05066
  7. [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. Zbl1079.05043

NotesEmbed ?

top

You must be logged in to post comments.