Premium
Packing k ‐edge trees in graphs of restricted vertex degrees
Author(s) -
Kelmans A.K.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20238
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , disjoint sets , neighbourhood (mathematics) , bound graph , discrete mathematics , graph power , line graph , mathematical analysis
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 (a1) if G ∈ ${\cal G}^{s}_{2}$ and s ≥ 4, then τ 2 ( G ) ≥ v ( G )/( s + 1), (a2) if G ∈ ${\cal G}^{3}_{2}$ and G has no 5‐vertex components, then τ 2 ( G ) ≥ v( G )4, (a3) 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 (a4) 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