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

DOI10.1007/s00493-020-3989-0zbMath1488.05426OpenAlexW3163212952MaRDI QIDQ2043762

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 graphundirected graphdiameter of a graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• 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\)
• Automorphism groups of circulant digraphs with applications to semigroup theory
• The Diameter of a Cycle Plus a Random Matching
• An Explicit Construction of Lower-Diameter Cubic Graphs
• Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)log _𝐾-1 𝑁 for each 𝐾-1 a prime power]

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