✦ LIBER ✦

On 2-Connected Spanning Subgraphs with Low Maximum Degree

✍ Scribed by Daniel P Sanders; Yue Zhao

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 408 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1836

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G, let a k-trestle of G be a 2-connected spanning subgraph of G of maximum degree at most k. Also, let /(G) be the Euler characteristic of G. This paper shows that every 3-connected graph G has a (10&2/(G))-trestle. If /(G) &5, this is improved to 8&2/(G), and for /(G) &10, this is further improved to 6&2/(G). This result is shown to be best possible for almost all values of /(G) by the demonstration of 3-connected graphs embedded on each surface of Euler characteristic / 0 which have no (5&2/)-trestle. Also, it is shown that a 4-connected graph embeddable on a surface with non-negative Euler characteristic has a 3-trestle, approaching a conjecture of Nash-Williams.

📜 SIMILAR VOLUMES

On spanning trees and walks of low maxim

On spanning trees and walks of low maximum degree

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB 👁 3 views

On low bound of degree sequences of span

On low bound of degree sequences of spanning trees inK-edge-connected graphs

✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.