DIMACS TR: 2000-44

Packing Trees in Graphes

Authors: Alexander Kelmans


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