Large Cayley graphs of small diameter

DOI10.1016/J.DAM.2018.04.025MaRDI QIDQ1801061zbMATH OpenOpenAlexWikidataFDO

Authors Grahame Erskine, James Tuite

Publication date 26 October 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.02425, http://oro.open.ac.uk/55855/1/LargeCayleyGraphs_arXiv_v2.pdf

zbMATH Keywords

Cayley graphsdegree-diameter problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: The degree-diameter problem seeks to find the largest possible number of vertices in a graph having given diameter and given maximum degree. Very often the problem is studied for restricted families of graph such as vertex-transitive or Cayley graphs, with the goal being to find a family of graphs with good asymptotic properties. In this paper we restrict attention to Cayley graphs, and study the asymptotics by fixing a small diameter and constructing families of graphs of large order for all values of the maximum degree. Much of the literature in this direction is focused on the diameter two case. In this paper we consider larger diameters, and use a variety of techniques to derive new best asymptotic constructions for diameters 3, 4 and 5 as well as an improvement to the general bound for all odd diameters. Our diameter 3 construction is, as far as we know, the first to employ matrix groups over finite fields in the degree-diameter problem.

Recommendations

• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• scientific article; zbMATH DE number 784887
• Cayley graphs of given degree and diameters 3, 4 and 5
• Large Cayley digraphs of given degree and diameter
• Large vertex-transitive and Cayley graphs with given degree and diameter

Cites work

• Cayley graphs of diameter two with order greater than \(0.684\) of the Moore bound for any degree
• Cayley graphs of given degree and diameters 3, 4 and 5
• Diameter 2 Cayley graphs of dihedral groups
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• Large Cayley digraphs of given degree and diameter
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• Large butterfly Cayley graphs and digraphs
• Moore graphs and beyond: a survey of the degree/diameter problem
• The difference between consecutive primes. II

Cited in

(15)

• Asymptotically approaching the Moore bound for diameter three by Cayley graphs
• Cayley graphs generated by small degree polynomials over finite fields
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• scientific article; zbMATH DE number 3891413 (Why is no real title available?)
• A note on large Cayley graphs of diameter two and given degree
• Large vertex-transitive and Cayley graphs with given degree and diameter
• Properties of groups for the cage and degree/diameter problems
• Cubic Cayley graphs with small diameter
• A note on a geometric construction of large Cayley graphs of given degree and diameter
• Diameter 2 Cayley graphs of dihedral groups
• Dense group networks
• scientific article; zbMATH DE number 784887 (Why is no real title available?)
• Exact upper bound for sorting \(R_n\) with LE
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• Large Cayley digraphs of given degree and diameter

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Large Cayley graphs of small diameter

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