Planar cubic graphs of small diameter

2019/08/15 by Knauer, Kolja, Micek, Piotr
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.05481

Abstract

Cubic planar n-vertex graphs with faces of length at most 6, e.g., fullerene graphs, have diameter in Ω(√(n)). It has been suspected, that a similar result can be shown for cubic planar graphs with faces of bounded length. This note provides a family of cubic planar n-vertex graphs with faces of length at most 7 and diameter in O(log n), thus refuting the above suspicion.

Related

• Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian
• Highly-connected planar cubic graphs with few or many Hamilton cycles
• Cubic graphs with large circumference deficit
• Hypohamiltonian planar cubic graphs with girth five
• Shortness coefficient of cyclically 4-edge-connected cubic graphs