Asymptotically approaching the Moore bound for diameter three by Cayley graphs

DOI10.1016/J.JCTB.2018.06.003MaRDI QIDQ1633751zbMATH OpenOpenAlexFDO

Authors Martin Bachratý, Jana Šiagiová, Jozef Širáň

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.09760, http://oro.open.ac.uk/55789/1/CayD3-JCTB-Fin.pdf

zbMATH Keywords

Cayley graphdiameterdegreegeneralised quadrangleSuzuki-Tits oval

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: The largest order $n(d,k)$ of a graph of maximum degree $d$ and diameter $k$ cannot exceed the Moore bound, which has the form $M(d,k)=d^k-O(d^{k-1})$ for $doinfty$ and any fixed $k$. Known results in finite geometries on generalised $(k+1)$-gons imply, for $k=2,3,5$, the existence of an infinite sequence of values of $d$ such that $n(d,k)=d^k-o(d^k)$. This shows that for $k=2,3,5$ the Moore bound can be asymptotically approached in the sense that $n(d,k)/M(d,k)o1$ as $doinfty$; moreover, no such result is known for any other value of $kge2$. The corresponding graphs are, however, far from vertex-transitive, and there appears to be no obvious way to extend them to vertex-transitive graphs giving the same type of asymptotic result. The second and the third author (2012) proved by a direct construction that the Moore bound for diameter $k=2$ can be asymptotically approached by Cayley graphs. Subsequently, the first and the third author (2015) showed that the same construction can be derived from generalised triangles with polarity. By a detailed analysis of regular orbits of suitable groups of automorphisms of graphs arising from polarity quotients of incidence graphs of generalised quadrangles with polarity, we prove that for an infinite set of values of $d$ there exist Cayley graphs of degree $d$, diameter $3$, and order $d^3-O(d^{2.5})$. The Moore bound for diameter $3$ can thus as well be asymptotically approached by Cayley graphs. We also show that this method does not extend to constructing Cayley graphs of diameter $5$ from generalised hexagons with polarity.

Recommendations

• 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
• Large Cayley graphs of small diameter
• Cayley graphs of given degree and diameters 3, 4 and 5
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter

Cites work

• scientific article; zbMATH DE number 5309966 (Why is no real title available?)
• scientific article; zbMATH DE number 1219619 (Why is no real title available?)
• scientific article; zbMATH DE number 3794103 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• Approaching the Moore bound for diameter two by Cayley graphs
• Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
• Cayley graphs of given degree and diameters 3, 4 and 5
• Cycle prefix digraphs for symmetric interconnection networks
• Diameter 2 Cayley graphs of dihedral groups
• Examples of products giving large graphs with given degree and diameter
• Finite generalized quadrangles
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• On Moore Graphs with Diameters 2 and 3
• On a Class of Fixed-Point-Free Graphs
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• Ovoides et groupes de Suzuki
• Polarity graphs revisited
• Structure of Ree groups
• Superfluous edges and exponential expansions of de Bruijn and Kautz graphs
• The maximal subgroups of the Chevalley groups \(G_ 2(q)\) with q odd, the Ree groups \(2G_ 2(q)\), and their automorphism groups

Cited in

(2)

• Approaching the Moore bound for diameter two by Cayley graphs
• On the nonexistence of lattice tilings of \(\mathbb{Z}^n\) by Lee spheres

This page was built for publication: Asymptotically approaching the Moore bound for diameter three by Cayley graphs

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