✦ LIBER ✦

Triangles with restricted degree sum of their boundary vertices in plane graphs

✍ Scribed by Oleg V. Borodin

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 373 KB
Volume: 137
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)e0144-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 vertices with restricted degree sum. As shown by constructions, if any of these assumptions is violated, the degree sum of each three pairwise adjacent vertices may be arbitrarily large. As for a quadruple of pairwise adjacent vertices, it can hardly be forced in a plane graph by means of any reasonable restrictions.

📜 SIMILAR VOLUMES

Subgraphs with restricted degrees of the

Subgraphs with restricted degrees of their vertices in planar graphs

✍ Igor Fabrici; Stanislav Jendrol' 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 335 KB

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. (~

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