Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds (Q1767631): Difference between revisions

If \(H\) is a subgraph of a graph \(G\), the weight of \(H\) in \(G\) is the sum of the degrees in \(G\) of all vertices of \(H\). Let \(S\) be a closed surface with Euler characteristic \(\chi(S) \leq 0\), and let \({\mathcal P}\) be the class of all graphs of minimum degree at least 5 that can be embedded in \(S\). It is shown that every graph \(G\) in \({\mathcal P}\) with at least \(83| \chi(S)| \) vertices contains a cycle of length 3 whose weight in \(G\) is at most 18. The weight 18 is shown to be best possible. As a corollary, a similar result is obtained for paths of lengths 1 and 2 instead of the 3-cycle. It is also shown that the weight of a path on three vertices can be lowered to 17 if \(G\) has enough vertices of degree more than 6. This is one of many papers on the same subject. An overview of known results can be found in two surveys written by the same authors [Light subgraphs of graphs embedded in the plane and in the projective plane---a survey, Discrete Math., to appear, and Bolyai Soc. Math. Stud. 11, 375--411 (2002; Zbl 1037.05015)].