DIMACS TR: 2000-44
Packing Trees in Graphes
Authors: Alexander Kelmans
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
$\tau _k (G)$ the maximum number of disjoint $k$--edge trees in $G$.
In this paper we show that
(a1) if $G \in {\cal G}^s_2 $ and $s \ge 4$ then $\tau _2 (G) \ge v(G)/(s+1)$,
(a2) if $G \in {\cal G}^3_2 $ and $G$ has no 5--vertex components then
$\tau _2 (G) \ge v(G)/4$,
(a3) if $G \in {\cal G}^s_1 $ and $G$ has no $k$--vertex component
where $k \ge 2$ and $s \ge 3$ then
$\tau _k(G) \ge (v(G) - k)/(sk - k +1)$, and
(a3) the above bounds are attained for infinitely many connected graphs.
Our proofs provide polynomial time algorithms for finding the corresponding
packings in a graph.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-44.ps.gz
DIMACS Home Page