Packingk-edge trees in graphs of restricted vertex degrees

DOI10.1002/JGT.20238MaRDI QIDQ3594953zbMATH OpenOpenAlexFDO

Authors Alexander Kelmans

Publication date 9 August 2007

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610384

zbMATH Keywords

subgraph packingpolynomial time approximation algorithms\(k\)-edge trees2-edge and \(k\)-edge paths

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

• Packing trees in complete graphs
• Packing and decomposition of graphs with trees
• Packing trees into complete \(k\)-partite graph
• On packing trees into complete bipartite graphs
• Packing trees in complete bipartite graphs
• Packing trees with constraints on the leaf degree
• scientific article; zbMATH DE number 22649
• Packing trees of bounded diameter into the complete graph
• Packing trees into \(n\)-chromatic graphs
• scientific article; zbMATH DE number 4063141

Cites work

• scientific article; zbMATH DE number 977446 (Why is no real title available?)
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Graph theory with applications

Cited in

(16)

• Packing branchings under cardinality constraints on their root sets
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
• \(H\)-packing of \(k\)-chromatic graphs
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• The k‐piece packing problem
• Packing and decomposition of graphs with trees
• Packing 3-vertex paths in claw-free graphs and related topics
• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• Edge-disjoint packings of graphs
• Constructing the spectrum for packings of the complete graph with trees that have up to five edges
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph
• Packing \([1, \Delta ]\)-factors in graphs of small degree
• Packing trees with constraints on the leaf degree

This page was built for publication: Packingk-edge trees in graphs of restricted vertex degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3594953)