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

DOI10.1016/J.EJC.2016.04.008zbMATH Open1339.05175arXiv1511.03706OpenAlexW2249111951MaRDI QIDQ298345FDOQ298345

Marcel Abas

Publication date: 20 June 2016

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

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.

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

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

zbMATH Keywords

networks design

Mathematics Subject Classification ID

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

Cites Work

• Moore graphs and beyond: a survey of the degree/diameter problem
• Title not available (Why is that?)
• Primes in arithmetic progressions
• On Graphs that do not Contain a Thomsen Graph
• On Moore Graphs with Diameters 2 and 3
• Maximum degree in graphs of diameter 2
• A note on large graphs of diameter two and given maximum degree
• A note on large Cayley graphs of diameter two and given degree
• Primes of prescribed congruence class in short intervals
• 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
• Title not available (Why is that?)
• Search for properties of the missing Moore graph

Cited In (4)

• Large Cayley graphs of small diameter
• Improved lower bounds on the degree-diameter problem
• Graphs of order two less than the Moore bound
• On the nonexistence of lattice tilings of \(\mathbb{Z}^n\) by Lee spheres

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)