# zbMATH — the first resource for mathematics

Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups. (English) Zbl 1232.05091
Summary: Let $$CC(d,2)$$ and $$AC(d,2)$$ be the largest order of a Cayley graph of a cyclic and an Abelian group, respectively, of diameter 2 and a given degree $$d$$. There is an obvious upper bound of the form $$CC(d,2)\leq AC(d,2)\leq d^{2}/2+d+1$$. We prove a number of lower bounds on both quantities for certain infinite sequences of degrees $$d$$ related to primes and prime powers, the best being $$CC(d,2)\geq (9/25)(d+3)(d - 2)$$ and $$AC(d,2)\geq (3/8)(d^{2} - 4)$$. We also offer a result for Cayley graphs of metacyclic groups for general degree and diameter.

##### MSC:
 05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text:
##### References:
  Bertram, E.; Herzog, M., On regular bases of finite groups, Amer. math. monthly, 103, 9, 796-799, (1996) · Zbl 0874.11015  Bridges, W.G.; Toueg, S., On the impossibility of directed Moore graphs, J. combin. theory ser. B, 29, 339-341, (1980) · Zbl 0388.05019  Canale, E.A.; Gómez, J., Asymptotically large $$(\Delta, D)$$-graphs, Discrete appl. math., 152, 1-3, 89-108, (2005) · Zbl 1080.05027  Conder, M.D.E.; Exoo, G.; Jajcay, R., On the limitations of the use of solvable groups in Cayley graph cage constructions, European J. combin., 31, 7, 1819-1828, (2010) · Zbl 1221.05198  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  Finkelstein, L.; Kleitman, D.; Leighton, T., Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures, (), 247-256  Garcia, C.; Peyrat, C., Large Cayley graphs on an abelian group, Discrete appl. math., 75, 2, 125-133, (1997) · Zbl 0880.05047  Kozma, G.; Lev, A., Bases and decomposition numbers of finite groups, Arch. math., 58, 417-424, (1992) · Zbl 0724.11005  Kozma, G.; Lev, A., On $$h$$-bases and $$h$$-decompositions of the finite solvable and alternating groups, J. number theory, 49, 385-391, (1994) · Zbl 0815.11009  Loz, E.; Širáň, J., New record graphs in the degree-diameter problem, Australas. J. combin., 41, 63-80, (2008) · Zbl 1178.05038  Macbeth, H.; Šiagiová, J.; Širáň, J.; Vetrík, T., Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter, J. graph theory, 64, 2, 87-98, (2010) · Zbl 1230.05158  B.D. McKay, Personal communication.  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, 110-118, (1998) · Zbl 0911.05031  Miller, M.; Širáň, J., Moore graphs and beyond: a survey of the degree-diameter problem, Electron. J. combin., dyn. surv., D14, (2005), 61pp · Zbl 1079.05043  On-line table of current largest graphs for the degree-diameter problem: http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem.  Rohrbach, H., Anwendung eines satzes der additiven zahlentheorie auf eine gruppentheoretische frage, Math. Z., 42, 538-542, (1937) · JFM 63.0066.02  Rohrbach, H., Ein beitrag zur additiven zahlentheorie, Math. Z., 42, 1-30, (1937) · JFM 62.1140.01  Šiagiová, J.; Širáň, J., A note on large Cayley graphs of diameter two and given degree, Discrete math., 305, 1-3, 379-382, (2005) · Zbl 1078.05037
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.