| Title:
|
A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles (English) |
| Author:
|
Mesežnikov, Dávid |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
3 |
| Year:
|
2012 |
| Pages:
|
518-521 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
the degree-diameter problem |
| Keyword:
|
voltage assignment and lift |
| Keyword:
|
dipole |
| MSC:
|
05C12 |
| MSC:
|
05C35 |
| idMR:
|
MR2975804 |
| . |
| Date available:
|
2012-08-31T15:59:38Z |
| Last updated:
|
2013-09-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142953 |
| . |
| Reference:
|
[1] Loz, E., Širáň, J.: New record graphs in the degree-diameter problem.Austral. J. Combin. 41 (2008), 63–80. Zbl 1178.05038, MR 2416966 |
| Reference:
|
[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. Zbl 1230.05158, MR 2664326 |
| Reference:
|
[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. Zbl 1232.05091, MR 2852512, 10.1016/j.disc.2011.03.038 |
| Reference:
|
[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. Zbl 0911.05031, MR 1644043, 10.1006/jctb.1998.1828 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1078.05037, MR 2186708, 10.1016/j.disc.2005.10.015 |
| Reference:
|
[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. Zbl 1046.05023, MR 1980377 |
| Reference:
|
[8] Šiagiová, J.: A note on the McKay-Miller-Širáň graphs.J. Combinat. Theory Ser. B 81 (2001), 205–208. Zbl 1024.05039, MR 1814904, 10.1006/jctb.2000.2006 |
| . |
