# 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

top

## Abstract

top
For any $d\ge 11$ we construct graphs of degree $d$, diameter $2$, and order $\frac{8}{25}{d}^{2}+O\left(d\right)$, 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\left(d\right)$ has been known [3] but it applies only to special values of degrees $d$ depending on prime powers.

## How to cite

top

Mesež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
1. Loz, E., Širáň, J., New record graphs in the degree-diameter problem, Austral. J. Combin. 41 (2008), 63–80. Zbl1178.05038MR2416966
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. Zbl1230.05158MR2664326
3. 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
4. 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
5. Miller, M., Širáň, J., Moore graphs and beyond: A survey of the degree/diameter problem, Electr. J. Combinatorics 2005, Dynamic Survey DS14. Zbl1079.05043
6. Š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
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. Zbl1046.05023MR1980377
8. Šiagiová, J., 10.1006/jctb.2000.2006, J. Combinat. Theory Ser. B 81 (2001), 205–208. Zbl1024.05039MR1814904DOI10.1006/jctb.2000.2006

## NotesEmbed?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.