×

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertram, E.; Herzog, M., On regular bases of finite groups, Amer. math. monthly, 103, 9, 796-799, (1996) · Zbl 0874.11015
[2] Bridges, W.G.; Toueg, S., On the impossibility of directed Moore graphs, J. combin. theory ser. B, 29, 339-341, (1980) · Zbl 0388.05019
[3] Canale, E.A.; Gómez, J., Asymptotically large \((\Delta, D)\)-graphs, Discrete appl. math., 152, 1-3, 89-108, (2005) · Zbl 1080.05027
[4] 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
[5] 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
[6] Finkelstein, L.; Kleitman, D.; Leighton, T., Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures, (), 247-256
[7] Garcia, C.; Peyrat, C., Large Cayley graphs on an abelian group, Discrete appl. math., 75, 2, 125-133, (1997) · Zbl 0880.05047
[8] Kozma, G.; Lev, A., Bases and decomposition numbers of finite groups, Arch. math., 58, 417-424, (1992) · Zbl 0724.11005
[9] 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
[10] Loz, E.; Širáň, J., New record graphs in the degree-diameter problem, Australas. J. combin., 41, 63-80, (2008) · Zbl 1178.05038
[11] 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
[12] B.D. McKay, Personal communication.
[13] 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
[14] 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
[15] On-line table of current largest graphs for the degree-diameter problem: http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem.
[16] Rohrbach, H., Anwendung eines satzes der additiven zahlentheorie auf eine gruppentheoretische frage, Math. Z., 42, 538-542, (1937) · JFM 63.0066.02
[17] Rohrbach, H., Ein beitrag zur additiven zahlentheorie, Math. Z., 42, 1-30, (1937) · JFM 62.1140.01
[18] Š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.