




















We investigate the minimum number of cycles of specified lengths in planar $n$-vertex triangulations $G$. It is proven that this number is $Ω(n)$ for any cycle length at most $3 + \max \{ {\rm rad}(G^*), \lceil (\frac{n-3}{2})^{\log_32} \rceil \}$, where ${\rm rad}(G^*)$ 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 $k \in \{ \lceil n - \sqrt[5]{n} \rceil, \ldots, n \}$. Furthermore, we prove that planar 4-connected $n$-vertex triangulations contain $Ω(n)$ many $k$-cycles for every $k \in \{ 3, \ldots, n \}$, and that, under certain additional conditions, they contain $Ω(n^2)$ $k$-cycles for many values of $k$, including $n$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。