Kybernetika 48 no. 3, 518-521, 2012

A construction of large graphs of diameter two and given degree from Abelian lifts of dipoles

Dávid Mesežnikov

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 \cite{MSS} but it applies only to special values of degrees $d$ depending on prime powers.

Keywords:

the degree-diameter problem, voltage assignment and lift, dipole

Classification:

05C12, 05C35

References:

  1. E. Loz and J. Širáň: New record graphs in the degree-diameter problem. Austral. J. Combin. 41 (2008), 63-80.   CrossRef
  2. H. Macbeth, J. Šiagiová, J. Širáň and T. Vetrík: Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter. J. Graph Theory 64 (2010), 2, 87-98.   CrossRef
  3. H. Macbeth, J. Šiagiová and J. Širáň: Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups. Discrete Math. 312 (2012), 1, 94-99.   CrossRef
  4. B. D. McKay, M. Miller and J. Širáň: A note on large graphs of diameter two and given maximum degree. J. Combinat. Theory Ser. B 74 (1998), 1, 110-118.   CrossRef
  5. M. Miller and J. Širáň: Moore graphs and beyond: A survey of the degree/diameter problem. Electr. J. Combinatorics 2005, Dynamic Survey DS14.   CrossRef
  6. J. Šiagiová and J. Širáň: A note on large Cayley graphs of diameter two and given degree. Discrete Math. 305 (2005), 1-3, 379-382.   CrossRef
  7. J. Šiagiová: 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.   CrossRef
  8. J. Šiagiová: A note on the McKay-Miller-Širáň graphs. J. Combinat. Theory Ser. B 81 (2001), 205-208.   CrossRef