Packing k‐edge trees in graphs of restricted vertex degrees |
| |
| Authors: | A.K. Kelmans |
| |
| Affiliation: | 1. University of Puerto Rico, San Juan Puerto Rico;2. Rutgers University, New Brunswick, New Jersey |
| |
| Abstract: | Let  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 ∈
 and s ≥ 4, then τ2(G) ≥ v(G)/(s + 1), - (a2) if G ∈
 and G has no 5‐vertex components, then τ2(G) ≥ v(G)4, - (a3) if G ∈
 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 |
| |
| Keywords: | subgraph packing 2‐edge and k‐edge paths k‐edge trees polynomial time approximation algorithms |
|
|
