An Explicit Construction of Lower-Diameter Cubic Graphs

DOI10.1137/S0895480197330266MaRDI QIDQ4443115zbMATH OpenOpenAlexFDO

Authors Michael Capalbo

Publication date 8 January 2004

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480197330266

zbMATH Keywords

diametershuffle-exchange graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• Constructions for cubic graphs with large girth
• Diameters of cubic graphs
• Cubic Cayley graphs with small diameter
• On the cubicity of certain graphs
• Cubical graphs and cubical dimensions
• Nonexistence of certain cubic graphs with small diameters
• A class of cubic graphs satisfying Berge conjecture
• scientific article; zbMATH DE number 714489
• On Polyhedral Embeddings of Cubic Graphs
• scientific article; zbMATH DE number 4002141

Cited in

(6)

• Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\)
• Maximal cubic graphs with diameter 4
• 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
• Pegging graphs yields a small diameter
• Explicit \(N\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)]\log_{K-1}N\) for each \(K-1\) a prime power
• Nonexistence of certain cubic graphs with small diameters

This page was built for publication: An Explicit Construction of Lower-Diameter Cubic Graphs

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