Light subgraphs of graphs embedded in the plane. A survey. (English) Zbl 1259.05045

Jendrol’, S.; Voss, H.-J.

Discrete Math. 313, No. 4, 406-421 (2013).

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

Keywords:

light subgraphs; weight of subgraph; plane graphs

Citations:

Zbl 0891.05025; Zbl 0916.05020