Light subgraphs of multigraphs on compact 2-dimensional manifolds (Q5936041): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:42, 30 January 2024
scientific article; zbMATH DE number 1612901
Language | Label | Description | Also known as |
---|---|---|---|
English | Light subgraphs of multigraphs on compact 2-dimensional manifolds |
scientific article; zbMATH DE number 1612901 |
Statements
Light subgraphs of multigraphs on compact 2-dimensional manifolds (English)
0 references
9 October 2002
0 references
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.
0 references
multigraph
0 references
3-connected
0 references
embedding
0 references
map
0 references
light subgraph
0 references