On light cycles in plane triangulations
type: Item
instance of: scholarly article
title: On light cycles in plane triangulations
zbMATH Open document ID: 0936.05065
DOI: 10.1016/S0012-365X(99)90099-7
author: Tomáš Madaras
author: Roman Soták
author: Zsolt Tuza
author: Stanislav Jendroľ
published in: Discrete Mathematics
publication date: 2000-02-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 52B10
zbMATH DE Number: 1322030
zbMATH Keywords: light cycles
zbMATH Keywords: light subgraphs
zbMATH Keywords: plane triangulations
reviewed by: Robert Jajcay
MaRDI profile type: Publication
cites work: Q3469114
cites work: On the total coloring of planar graphs.
cites work: Triangles with restricted degree sum of their boundary vertices in plane graphs
cites work: Minimal vertex degree sum of a 3-path in plane maps
cites work: On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
cites work: Short cycles of low weight in normal plane maps with minimum degree 5
cites work: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
cites work: On vertex-degree restricted paths in polyhedral graphs
cites work: Q4117038
cites work: Q4085741
cites work: Paths with restricted degrees of their vertices in planar graphs
cites work: On light subgraphs in plane graphs of minimum degree five
cites work: Q5344765
full work available at URL: s0012-365x(99)90099-7
OpenAlex ID: W4210570893
description: scientific article; zbMATH DE number 1322030