𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subgraphs with restricted degrees of their vertices in planar graphs

✍ Scribed by Igor Fabrici; Stanislav Jendrol'

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
335 KB
Volume
191
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every 3-connected planar graph G of order at least k contains a connected subgraph H on k vertices each of which has degree (in G) at most 4k + 3, the bound 4k + 3 being best possible. (~

πŸ“œ SIMILAR VOLUMES

Subgraphs with Restricted Degrees of the
Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds
✍ S. Jendrol’; H.-J. Voss πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 276 KB

Let k β‰₯ 2, be an integer and M be a closed two-manifold with Euler characteristic Ο‡(M) ≀ 0. We prove that each polyhedral map G on M, which has at least (8k 2 + 6k -6)|Ο‡ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4k

Triangles with restricted degree sum of
Triangles with restricted degree sum of their boundary vertices in plane graphs
✍ Oleg V. Borodin πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 373 KB

It is known that under appropriate assumptions, each plane graph contains a vertex of degree at most 5 and a pair of adjacent vertices with degree sum at most 13. Two structural assumptions are established for a plane graph which together guarantee the existence of a triple of pairwise adjacent vert

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 213 KB πŸ‘ 2 views

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 sh

Light subgraphs in planar graphs of mini
Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9
✍ B. Mohar; R. Ε krekovski; H.-J. Voss πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 326 KB πŸ‘ 1 views

## 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