Premium
Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
Author(s) -
Mohar B.,
Škrekovski R.,
Voss H.J.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10144
Subject(s) - combinatorics , mathematics , degree (music) , planar graph , graph , diagonal , discrete mathematics , geometry , physics , acoustics
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 C s is light if and only if 3 ≤ s ≤ 6, where w ( C 3 ) = 21 and w ( C 4 ) ≤ 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 K 1, s is light if and only if s ≤ 4. In particular, w ( K 1,3 ) = 23. The paths P s are light for 1 ≤ s ≤ 6, and heavy for s ≥ 8. Moreover, w ( P 3 ) = 17 and w ( P 4 ) = 23. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 261–295, 2003