๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D

โœ Scribed by Pankaj K. Agarwal; Rolf Klein; Christian Knauer; Stefan Langerman; Pat Morin; Micha Sharir; Michael Soss

Publisher
Springer
Year
2007
Tongue
English
Weight
466 KB
Volume
39
Category
Article
ISSN
0179-5376

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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