On light cycles in plane triangulations (Q1292852): Difference between revisions

A graph \(H\) is said to be light in the class of graphs \({\mathcal G}\) if there exists a positive integer \(k\) such that each graph \(G\in{\mathcal G}\) that contains an isomorphic copy of \(H\) contains a subgraph \(K\) isomorphic to \(H\) that satisfies the inequality \(\deg_G(v)\leq k\), for all vertices \(v\) of \(K\). The smallest positive integer \(k\) with this property is denoted by \(\varphi(H,{\mathcal G})\). In the main result of the paper, the authors present a complete classification of cycles \(C_r\) that are light in the class \({\mathcal T}(5)\) of plane triangulations with minimum degree 5, namely, they show that a cycle \(C_r\) is light in \({\mathcal T}(5)\) if and only if \(r\in\{3, 4, 5, 6, 7, 8, 9, 10\}\). As for the numbers \(\varphi(C_r,{\mathcal T}(5))\), they show that \(10\leq \varphi(C_6,{\mathcal T}(5))\leq 11\), \(15\leq\varphi(C_7,{\mathcal T}(5))\leq 17\), \(15\leq \varphi(C_8,{\mathcal T}(5))\leq 29\), \(19\leq \varphi(C_9,{\mathcal T}(5))\leq 41\), \(20\leq \varphi(C_{10},{\mathcal T}(5))\leq 415\) (the remaining three identities are \(\varphi(C_3,{\mathcal T}(5))= 7\), \(\varphi(C_4,{\mathcal T}(5))= 10\), \(\varphi(C_5,{\mathcal T}(5))= 10\); the last two have been shown by \textit{S. Jendrol'} and \textit{T. Madaras} [Discuss. Math., Graph Theory 16, No. 2, 207-217 (1996; Zbl 0877.05050)]; \(C_{10}\) has been shown to be light in \({\mathcal T}(5)\) by T. Madaras ans R. Soták). Most of the paper is devoted to proving the theorem. The proofs of the fact that none of the \(C_r\)'s with \(r>10\) is light in \({\mathcal T}(5)\) and of the lower bounds are constructive. The upper bounds are the result of a clever application of a ``discharge method'' to the hypothetical counterexamples.