Planar cubic graphs of small diameter

arXiv1908.05481MaRDI QIDQ6323693FDOQ6323693

Authors: Kolja Knauer, Piotr Micek 

Publication date: 15 August 2019

Abstract: Cubic planar $n$-vertex graphs with faces of length at most $6$, e.g., fullerene graphs, have diameter in $Omega(sqrtn)$. 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(logn)$, thus refuting the above suspicion.

This page was built for publication: Planar cubic graphs of small diameter

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