Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
Bojan Mohar, Riste Škrekovski, H.‐J. Voss · Journal of Graph Theory · 2003
Abstract A graph H is light in a given class of graphs if there is a constant w such that every graph of the class which has a subgraph isomorphic to H also has a subgraph isomorphic to H whose sum of degrees in G is ≤ w. Let $\cal G$ be the class of simple planar graphs of minimum degree ≥ 4 in which no two vertices of degree 4 are adjacent. We denote the minimum such w by w(H). It is proved that the cycle Cs is light if and only if 3 ≤ s ≤ 6, where w(C3) = 21 and w(C4) ≤ 35. The 4‐cycle with one diagonal is not light in $\cal G$ , but it is light in the subclass ${\cal G}^T$ consisting of all triangulations. The star K1,s is light if and only if s ≤ 4. In particular, w(K1,3) = 23. The paths Ps are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w(P3) = 17 and w(P4) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003