2006/10/11 by Alexander Kelmans, Kelmans, Alexander
Computer Science · Engineering · Mathematics · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Packing Problems #math.CO #msc:05C10
paper · pdf · doi:10.48550/arxiv.math/0610384
14 pages
arxiv created 2006/10/11 · openalex publication_date 2006/10/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let v(G) be the number of vertices and t(G,k) the maximum number of disjoint k-edge trees in G. In this paper we show that (a1) if G is a graph with every vertex of degree at least two and at most s, where s > 3, then t(G,2) is at least v(G)/(s+1), (a2) if G is a graph with every vertex of degree at least two and at most 3 and G has no 5-vertex components, then t(G,2) is at least v(G)/4, (a3) if G is a graph with every vertex of degree at least one and at most s and G has no k--vertex component, where k >1 and s > 2, then t(G,k) is at least (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. Keywords: subgraph packing, 2-edge and k-edge paths, k-edge trees, polynomial time approximation algorithms.