Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
type: Item
instance of: scholarly article
title: Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
zbMATH Open document ID: 1077.05029
published in: European Journal of Combinatorics
publication date: 2005-03-08T00:00:00Z
review text: 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)].
reviewed by: Bojan Mohar
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 2142217
zbMATH Keywords: light graph
zbMATH Keywords: embedding
zbMATH Keywords: surfaces
zbMATH Keywords: polyhedral map
author: Stanislav Jendroľ
author: Heinz-Juergen Voss
MaRDI profile type: Publication
full work available at URL: j.ejc.2004.01.013
OpenAlex ID: W2048092776
cites work: Q3469114
cites work: Short cycles of low weight in normal plane maps with minimum degree 5
cites work: On vertex-degree restricted paths in polyhedral graphs
cites work: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
cites work: On light graphs in the family of 4-connected planar graphs
cites work: Q4027161
cites work: On light subgraphs in plane graphs of minimum degree five
cites work: On light cycles in plane triangulations
cites work: Q4680310
cites work: A local property of polyhedral maps on compact two-dimensional manifolds
cites work: A local property of large polyhedral maps on compact 2-dimensional manifolds
cites work: Light paths with an odd number of vertices in large polyhedral maps
cites work: Light subgraphs of multigraphs on compact 2-dimensional manifolds
cites work: Q4529514
cites work: Q4410027
cites work: Light subgraphs of graphs embedded in the plane. A survey
cites work: Q4432940
cites work: Q4812872
cites work: Q4518403
cites work: Face-width of embedded graphs
cites work: Light paths in 4-connected graphs in the plane and other surfaces
cites work: Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
cites work: Q4773723
cites work: Q3972954
cites work: Q5650693
cites work: On light edges and triangles in projective planar graphs
DOI: 10.1016/J.EJC.2004.01.013
description: scientific article; zbMATH DE number 2142217