Partitions and Coverings of Trees by Bounded-Degree Subtrees

Details Partitions and Coverings of Trees by Bounded-Degree Subtrees Partitions and Coverings of Trees by Bounded-Degree Subtrees

2010-08-19

arxiv.org/abs/1008.3190v1

Mathematics

Combinatorics

Scientific paper

This paper addresses the following questions for a given tree $T$ and integer $d\geq2$: (1) What is the minimum number of degree-$d$ subtrees that partition $E(T)$? (2) What is the minimum number of degree-$d$ subtrees that cover $E(T)$? We answer the first question by providing an explicit formula for the minimum number of subtrees, and we describe a linear time algorithm that finds the corresponding partition. For the second question, we present a polynomial time algorithm that computes a minimum covering. We then establish a tight bound on the number of subtrees in coverings of trees with given maximum degree and pathwidth. Our results show that pathwidth is the right parameter to consider when studying coverings of trees by degree-3 subtrees. We briefly consider coverings of general graphs by connected subgraphs of bounded degree.

Affiliated with

Also associated with

No associations

Rating

Partitions and Coverings of Trees by Bounded-Degree Subtrees 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 Partitions and Coverings of Trees by Bounded-Degree Subtrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitions and Coverings of Trees by Bounded-Degree Subtrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-134428