An explicit infinite family of M-vertex graphs with maximum degree K and diameter [1+o(1)]_K-1M for each K-1 a prime power

DOI10.1007/S00493-020-3989-0MaRDI QIDQ2043762zbMATH OpenOpenAlexFDO

Authors Michael Capalbo

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-020-3989-0

zbMATH Keywords

cubic graphdiameter of a graphundirected graph

Mathematics Subject Classification ID

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

Review text

The solution of a long-standing open question is presented by giving an explicit construction of an infinite family of \(\mathbb{M}\)-vertex cubic graphs that have diameter \([1+o(1)]\log_{K-1}\mathbb{M}\). For every \(K = p^s + 1\), where \(p\) is any prime number (including \(2\)) and \(s\) any positive integer, the author extends the techniques to construct an infinite family of \(K\)-regular graphs on \(\mathbb{M}\) vertices with diameter \([1+o(1)]\log_{K-1}\mathbb{M}\).

Recommendations

• Explicit \(N\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}N\) for each \(K-1\) a prime power
• An Explicit Construction of Lower-Diameter Cubic Graphs
• A note on large graphs of diameter two and given maximum degree
• Some large graphs with given degree and diameter
• Maximal cubic graphs with diameter 4

Cites work

• An Explicit Construction of Lower-Diameter Cubic Graphs
• Automorphism groups of circulant digraphs with applications to semigroup theory
• Cubic Ramanujan graphs
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit \(N\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}N\) for each \(K-1\) a prime power
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• Ramanujan graphs
• The Diameter of a Cycle Plus a Random Matching

Cited in

(2)

• Explicit \(N\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}N\) for each \(K-1\) a prime power
• The Problem of a Symmetric Graph with a Maximum Number of Vertices and Minimum Diameter

This page was built for publication: An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power

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