Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
the degree-diameter problem; voltage assignment and lift; dipole
the degree-diameter problem; voltage assignment and lift; dipole
Summary:
For any $d\ge 11$ we construct graphs of degree $d$, diameter $2$, and order $\frac{8}{25}d^2+O(d)$, obtained as lifts of dipoles with voltages in cyclic groups. For Cayley Abelian graphs of diameter two a slightly better result of $\frac{9}{25}d^2 + O(d)$ has been known [3] but it applies only to special values of degrees $d$ depending on prime powers.
References:
[1] Loz, E., Širáň, J.: New record graphs in the degree-diameter problem. Austral. J. Combin. 41 (2008), 63–80. MR 2416966 | Zbl 1178.05038
[2] 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 (2010), 2, 87–98. MR 2664326 | Zbl 1230.05158
[3] Macbeth, H., Šiagiová, J., Širáň, J.: Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups. Discrete Math. 312 (2012), 1, 94–99. DOI 10.1016/j.disc.2011.03.038 | MR 2852512 | Zbl 1232.05091
[4] McKay, B. D., Miller, M., Širáň, J.: A note on large graphs of diameter two and given maximum degree. J. Combinat. Theory Ser. B 74 (1998), 1, 110–118. DOI 10.1006/jctb.1998.1828 | MR 1644043 | Zbl 0911.05031
[5] Miller, M., Širáň, J.: Moore graphs and beyond: A survey of the degree/diameter problem. Electr. J. Combinatorics 2005, Dynamic Survey DS14. Zbl 1079.05043
[6] Šiagiová, J., Širáň, J.: A note on large Cayley graphs of diameter two and given degree. Discrete Math. 305 (2005), 1–3, 379–382. DOI 10.1016/j.disc.2005.10.015 | MR 2186708 | Zbl 1078.05037
[7] Šiagiová, J.: A Moore-like bound for graphs of diameter 2 and given degree obtained as Abelian lifts of dipoles. Acta Math. Univ. Comen. 71 (2002), 2, 157–161. MR 1980377 | Zbl 1046.05023
[8] Šiagiová, J.: A note on the McKay-Miller-Širáň graphs. J. Combinat. Theory Ser. B 81 (2001), 205–208. DOI 10.1006/jctb.2000.2006 | MR 1814904 | Zbl 1024.05039
Search
Partner of
