Geodesic
A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
Kybernetika, Tome 48 (2012) no. 3, pp. 518-521 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C12, 05C35
Keywords: the degree-diameter problem; voltage assignment and lift; dipole 
@article{KYB_2012_48_3_a11,
     author = {Mese\v{z}nikov, D\'avid},
     title = {A construction of large graphs of diameter two and given degree from {Abelian} lifts of dipoles},
     journal = {Kybernetika},
     pages = {518--521},
     year = {2012},
     volume = {48},
     number = {3},
     mrnumber = {2975804},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a11/}
}
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
SP  - 518
EP  - 521
VL  - 48
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a11/
LA  - en
ID  - KYB_2012_48_3_a11
ER  - 
%0 Journal Article
%A Mesežnikov, Dávid
%T A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles
%J Kybernetika
%D 2012
%P 518-521
%V 48
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a11/
%G en
%F KYB_2012_48_3_a11
Mesežnikov, Dávid. A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles. Kybernetika, Tome 48 (2012) no. 3, pp. 518-521. http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a11/

[1] Loz, E., Širáň, J.: New record graphs in the degree-diameter problem. Austral. J. Combin. 41 (2008), 63–80. | MR | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[5] Miller, M., Širáň, J.: Moore graphs and beyond: A survey of the degree/diameter problem. Electr. J. Combinatorics 2005, Dynamic Survey DS14. | Zbl

[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 | MR | Zbl

[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 | Zbl

[8] Šiagiová, J.: A note on the McKay-Miller-Širáň graphs. J. Combinat. Theory Ser. B 81 (2001), 205–208. | DOI | MR | Zbl