Packing k-edge trees in graphs of restricted vertex degrees

✍ Scribed by A.K. Kelmans

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 368 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20238

✦ Synopsis

Abstract

Let ${\cal G}^{s}_{r}$ denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τ~k~ (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that

if G ∈ ${\cal G}^{s}_{2}$ and s ≥ 4, then τ~2~(G) ≥ v(G)/(s + 1),

if G ∈ ${\cal G}^{3}_{2}$ and G has no 5‐vertex components, then τ~2~(G) ≥ v(G)4,

if G ∈ ${\cal G}^{s}_{1}$ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τ~k~(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and

the above bounds are attained for infinitely many connected graphs.

Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007