✦ LIBER ✦

2-connected coverings of bounded degree in 3-connected graphs

✍ Scribed by Zhicheng Gao

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 572 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200309

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In a recent paper, Barnette showed that every 3‐connected planar graph has a 2‐connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2‐connected spanning subgraphs of maximum degree five. In this paper, we show that every 3‐connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2‐connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

2-connected 7-coverings of 3-connected g

2-connected 7-coverings of 3-connected graphs on surfaces

✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract An __m__‐__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus __k__ ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log

On locating cubic subgraphs in bounded-d

On locating cubic subgraphs in bounded-degree connected bipartite graphs

✍ Iain A Stewart 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 236 KB

We show that the problem of deciding whether a connected bipartite graph of degree at most 4 has a cubic subgraph is NP-complete.

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

Degree bounds for the circumference of 3

Degree bounds for the circumference of 3-connected graphs

✍ Heinz A. Jung; Elkin Vumar 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB 👁 1 views

## Abstract Let __C__ be a longest cycle in the 3‐connected graph __G__ and let __H__ be a component of __G__ − __V__(__C__) such that |__V__(__H__)| ≥ 3. We supply estimates of the form |__C__| ≥ 2__d__(__u__) + 2__d__(__v__) − α(4 ≤ α ≤ 8), where __u__,__v__ are suitably chosen non‐adjacent verti

2-Connected Spanning Subgraphs of Planar

2-Connected Spanning Subgraphs of Planar 3-Connected Graphs

✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.