Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650714 | Discrete Mathematics | 2006 | 9 Pages |
Abstract
A n -vertex graph is said to be decomposable if for any partition (λ1,…,λp)(λ1,…,λp) of the integer n , there exists a sequence (V1,…,Vp)(V1,…,Vp) of connected vertex-disjoint subgraphs with |Vi|=λi|Vi|=λi. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dominique Barth, Hervé Fournier,