×

zbMATH — the first resource for mathematics

Light subgraphs of graphs embedded in the plane. A survey. (English) Zbl 1259.05045
Summary: It is well known that every planar graph contains a vertex of degree at most 5. A theorem of Kotzig states that every 3-connected planar graph contains an edge whose endvertices have degree-sum at most 13. I. Fabrici and S. Jendrol’ [Graphs Comb. 13, No. 3, 245–250 (1997; Zbl 0891.05025)] proved that every 3-connected planar graph \(G\) that contains a \(k\)-vertex path contains also a \(k\)-vertex path \(P\) such that every vertex of \(P\) has degree at most \(5k\). A result by H. Enomoto and K. Ota [J. Graph Theory 30, No. 3, 191–203 (1999; Zbl 0916.05020)] says that every 3-connected planar graph \(G\) of order at least \(k\) contains a connected subgraph \(H\) of order \(k\) such that the degree sum of vertices of \(H\) in \(G\) is at most \(8k-1\).
Motivated by these results, a concept of light graphs has been introduced. A graph \(H\) is said to be light in a family \(\mathcal{G}\) of graphs if at least one member of \(\mathcal G\) contains a copy of \(H\) and there is an integer \(w(H,\mathcal{G})\) such that each member \(G\) of \(\mathcal{G}\) with a copy of \(H\) also has a copy \(K\) of \(H\) such that \(\sum_{v \in V(K)} \deg_{G}(v) \leq w(H,\mathcal{G})\).
In this paper we present a survey of results on light graphs in different families of plane graphs and multigraphs. A similar survey dealing with the family of all graphs embedded in surfaces other than the sphere was prepared as well.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C22 Signed and weighted graphs
PDF BibTeX XML Cite
Full Text: DOI