Counting cycles in planar triangulations

arXiv2210.01190MaRDI QIDQ6412786FDOQ6412786

Authors: On-Hei S. Lo, Carol T. Zamfirescu 

Publication date: 3 October 2022

Abstract: We investigate the minimum number of cycles of specified lengths in planar $n$-vertex triangulations $G$. It is proven that this number is $Omega(n)$ for any cycle length at most $3+maxmrad(G^{\ast }),lceil(fracn-32{)}^{lo{g}_{3}2}ceil$, where $mrad(G^{\ast })$ denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian $n$-vertex triangulations containing $O(n)$ many $k$-cycles for any $kinlceiln-sqrt[5]nceil,ldots,n$. Furthermore, we prove that planar 4-connected $n$-vertex triangulations contain $Omega(n)$ many $k$-cycles for every $kin3,ldots,n$, and that, under certain additional conditions, they contain $Omega(n^2)$ $k$-cycles for many values of $k$, including $n$.

This page was built for publication: Counting cycles in planar triangulations

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