×

zbMATH — the first resource for mathematics

A note on large Cayley graphs of diameter two and given degree. (English) Zbl 1078.05037
Summary: For a variety of infinite sets of positive integers \(d\) related to odd prime powers we describe a simple construction of Cayley graphs of diameter two and given degree \(d\) which have order close to \(d^{2}/2\).

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brown, W.G., On graphs that do not contain a thompsen graph, Canad. math. bull., 9, 281-285, (1966) · Zbl 0178.27302
[2] Dinneen, M.J.; Hafner, P.R., New results for the degree/diameter problem, Networks, 24, 359-367, (1994) · Zbl 0806.05039
[3] Dougherty, R.; Faber, V., The degree-diameter problem for several varieties of Cayley graphs, I: the abelian case, SIAM J. discrete math., 17, 3, 478-519, (2004) · Zbl 1056.05046
[4] Hafner, P.R., Large Cayley graphs and digraphs with small degree and diameter, (), 291-302 · Zbl 0830.05025
[5] Hoffman, A.J.; Singleton, R.R., On Moore graphs with diameter 2 and 3, IBM J. res. develop., 4, 497-504, (1960) · Zbl 0096.38102
[6] McKay, B.D.; Miller, M.; Širáň, J., A note on large graphs of diameter two and given maximum degree, J. combin. theory ser. B, 74, 1, 110-118, (1998) · Zbl 0911.05031
[7] M. Miller, J. Širáň, Moore graphs and beyond: a survey, Preprint, submitted for publication.
[8] Šiagiová, J., A note on the mckay – miller-širáň graphs, J. combin. theory ser. B, 81, 205-208, (2001) · Zbl 1024.05039
[9] Šiagiová, J., A Moore-like bound for graphs of diameter 2 and given degree, obtained as abelian lifts of dipoles, Acta math. univ. Comenian., 71, 2, 157-161, (2002) · Zbl 1046.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.