Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree

DOI10.1016/J.EJC.2016.04.008MaRDI QIDQ298345zbMATH OpenOpenAlexFDO

Authors Marcel Abas

Publication date 20 June 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03706

zbMATH Keywords

networks design

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: It is known that the number of vertices of a graph of diameter two cannot exceed $d^2+1$. In this contribution we give a new lower bound for orders of Cayley graphs of diameter two in the form $C(d,2)>0.684d^2$ valid for all degrees $dgeq360756$. The result is a significant improvement of currently known results on the orders of Cayley graphs of diameter two.

Recommendations

• Cayley graphs of diameter two and any degree with order half of the Moore bound
• Cayley graphs of diameter 2 from difference sets
• Approaching the Moore bound for diameter two by Cayley graphs
• Improved lower bounds on the degree-diameter problem
• Diameter 2 Cayley graphs of dihedral groups

Cites work

• A note on large Cayley graphs of diameter two and given degree
• A note on large graphs of diameter two and given maximum degree
• Approaching the Moore bound for diameter two by Cayley graphs
• Cayley graphs of diameter two and any degree with order half of the Moore bound
• scientific article; zbMATH DE number 2152953 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• Maximum degree in graphs of diameter 2
• Moore graphs and beyond: a survey of the degree/diameter problem
• On Graphs that do not Contain a Thomsen Graph
• On Moore Graphs with Diameters 2 and 3
• Primes in arithmetic progressions
• Primes of prescribed congruence class in short intervals
• Search for properties of the missing Moore graph

Cited in

(11)

• Almost all Cayley graphs have diameter 2
• Large Cayley graphs of small diameter
• On diameter two Cayley graphs
• Diameter 2 Cayley graphs of dihedral groups
• Improved lower bounds on the degree-diameter problem
• On the nonexistence of lattice tilings of \(\mathbb{Z}^n\) by Lee spheres
• Infinite families of graphs with diameter two
• Cayley graphs of diameter two and any degree with order half of the Moore bound
• Approaching the Moore bound for diameter two by Cayley graphs
• Cayley graphs of diameter 2 from difference sets
• Graphs of order two less than the Moore bound

This page was built for publication: Cayley graphs of diameter two with order greater than \(0.684\) of the Moore bound for any degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q298345)