# 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

top## How 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 ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.