Packing k-edge Trees in Graphs of Restricted Vertex Degrees

Details Packing k-edge Trees in Graphs of Restricted Vertex Degrees Packing k-edge Trees in Graphs of Restricted Vertex Degrees

2006-10-11

arxiv.org/abs/math/0610384v1

Mathematics

Combinatorics

14 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Packing k-edge Trees in Graphs of Restricted Vertex Degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Packing k-edge Trees in Graphs of Restricted Vertex Degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packing k-edge Trees in Graphs of Restricted Vertex Degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-443064