A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
Kybernetika (2012)
- Volume: 48, Issue: 3, page 518-521
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topMesežnikov, Dávid. "A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles." Kybernetika 48.3 (2012): 518-521. <http://eudml.org/doc/246890>.
@article{Mesežnikov2012,
abstract = {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.},
author = {Mesežnikov, Dávid},
journal = {Kybernetika},
keywords = {the degree-diameter problem; voltage assignment and lift; dipole; the degree-diameter problem; voltage assignment and lift; dipole},
language = {eng},
number = {3},
pages = {518-521},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles},
url = {http://eudml.org/doc/246890},
volume = {48},
year = {2012},
}
TY - JOUR
AU - Mesežnikov, Dávid
TI - A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 3
SP - 518
EP - 521
AB - 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.
LA - eng
KW - the degree-diameter problem; voltage assignment and lift; dipole; the degree-diameter problem; voltage assignment and lift; dipole
UR - http://eudml.org/doc/246890
ER -
References
top- Loz, E., Širáň, J., New record graphs in the degree-diameter problem, Austral. J. Combin. 41 (2008), 63–80. Zbl1178.05038MR2416966
- 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. Zbl1230.05158MR2664326
- Macbeth, H., Šiagiová, J., Širáň, J., 10.1016/j.disc.2011.03.038, Discrete Math. 312 (2012), 1, 94–99. Zbl1232.05091MR2852512DOI10.1016/j.disc.2011.03.038
- McKay, B. D., Miller, M., Širáň, J., 10.1006/jctb.1998.1828, J. Combinat. Theory Ser. B 74 (1998), 1, 110–118. Zbl0911.05031MR1644043DOI10.1006/jctb.1998.1828
- Miller, M., Širáň, J., Moore graphs and beyond: A survey of the degree/diameter problem, Electr. J. Combinatorics 2005, Dynamic Survey DS14. Zbl1079.05043
- Šiagiová, J., Širáň, J., 10.1016/j.disc.2005.10.015, Discrete Math. 305 (2005), 1–3, 379–382. Zbl1078.05037MR2186708DOI10.1016/j.disc.2005.10.015
- Š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. Zbl1046.05023MR1980377
- Šiagiová, J., 10.1006/jctb.2000.2006, J. Combinat. Theory Ser. B 81 (2001), 205–208. Zbl1024.05039MR1814904DOI10.1006/jctb.2000.2006
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.