Light subgraphs of multigraphs on compact 2-dimensional manifolds (Q5936041): Difference between revisions

The topic of this paper is a classical problem concerning the finding of upper bounds for the total of degrees of some fixed subgraph \(G\) that hold for at least one occurrence of \(G\) in any topological embedding belonging to a particular ``interesting'' class and containing at least one copy of \(G\) (the best known example being the graph \(G\) consisting of a single edge with respect to the class of 3-connected planar graphs, considered by Kotzig). The subgraphs \(G\) for which such upper bounds exist are called light, and this paper is a continuation of a series of articles devoted to light paths in various classes of embeddings. The authors prove that each 3-connected multigraph \(G\) without loops and trivial 2-cycles embedded into a compact 2-dimensional manifold of a non-positive Euler characteristic \( \chi\) that contains a \(k\)-path (\(k\) being the number of vertices) contains also a \(k\)-path with each vertex of degree at most \(6k(1-\chi /3) \), for \(k\) even, or \( (6k-2)(1-\chi /3)\), for \(k \geq 3\) odd. They show that these bounds are sharp, and, moreover, no other graphs other than \(k\)-paths are light in this class. Thus, the situation is rather similar to several other classes considered previously by the authors for which the paper can serve as a quick overview. The methods used are also similar to those used in their other papers, and they promise to produce further results along these lines.