×

Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter. (English) Zbl 1230.05158

Summary: For any \(d \geq 5\) and \(k \geq 3\) we construct a family of Cayley graphs of degree \(d\), diameter \(k\), and order at least \(k((d - 3)/3)^k\). By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C07 Vertex degrees
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Comellas, Vertex-symmetric digraphs with small diameter, Discrete Applied Math 58 (1) pp 1– (1995) · Zbl 0822.05033
[2] Dixon, Permutation Groups (1996)
[3] Dougherty, The degree-diameter problem for several varieties of Cayley graphs, I: The Abelian case, SIAM J Discrete Math 17 (3) pp 478– (2004) · Zbl 1056.05046
[4] Gómez, On large vertex-symmetric digraphs, Discrete Math · Zbl 1225.05112
[5] Loz, New record graphs in the degree-diameter problem, Australas J Combin 41 pp 63– (2008) · Zbl 1178.05038
[6] Faber, Cycle prefix digraphs for symmetric interconnection networks, Networks 23 pp 641– (1993) · Zbl 0802.90043
[7] Garcia, Large Cayley graphs on an abelian group, Discrete Applied Math 75 (2) pp 125– (1997) · Zbl 0880.05047
[8] Jones, Automorphisms and regular embeddings of merged Johnson graphs, Europ J Combin 26 pp 417– (2005) · Zbl 1063.05037
[9] Miller, Moore graphs and beyond: A survey of the degree-diameter problem, Electr J Comb (2005) · Zbl 1079.05043
[10] McKay, A note on large graphs of diameter two and given maximum degree, J Combin Theory Ser B 74 (1) pp 110– (1998) · Zbl 0911.05031
[11] Šiagiová, A note on large Cayley graphs of diameter two and given degree, Discrete Math 305 (1-3) pp 379– (2005)
[12] M. Ždímalová, A note on constructions of Comellas-Fiol and Gómez, submitted.
[13] M. Ždímalová, Revisiting the Comellas-Fiol-Gómez construction of large digraphs of given degree and diameter, submitted.
[14] Largest vertex-transitive graphs of ”small” degree and diameter, at http://www.math.auckland.ac.nz/eloz002/degreediameter/.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.