Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Scribed by Enomoto, Hikoe; Ota, Katsuhiro
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 213 KB
- Volume
- 30
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3-connected planar graph G with |V (G)| ≥ t has a connected subgraph H of order t such that x∈V (H) deg G (x) ≤ 8t -1. As a tool for proving this result, we consider decompositions of 3-connected planar graphs into connected subgraphs of order at least t and at most 2t -1.