Discussiones Mathematicae Graph Theory 26(2) (2006)
291-305
DOI: https://doi.org/10.7151/dmgt.1321
ARBITRARILY VERTEX DECOMPOSABLE CATERPILLARS WITH FOUR OR FIVE LEAVES
Sylwia Cichacz, Agnieszka Görlich, Antoni Marczyk, Jakub Przybyło
Faculty of Applied Mathematics | Mariusz Woźniak
Institute of Mathematics of Polish Academy of Sciences |
Abstract
A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a1,☐,ak) of positive integers such that a1+☐+ak = n there exists a partition (V1,☐,Vk) of the vertex set of G such that for each i ∈ {1,☐,k}, Vi induces a connected subgraph of G on ai vertices.D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable caterpillars with four leaves. We also describe two families of arbitrarily vertex decomposable trees with maximum degree three or four.
Keywords: arbitrarily vertex decomposable graphs, trees, caterpillars, star-like trees.
2000 Mathematics Subject Classification: 05C70.
References
[1] | D. Barth, O. Baudon and J. Puech, Decomposable trees: a polynomial algorithm for tripodes, Discrete Appl. Math. 119 (2002) 205-216, doi: 10.1016/S0166-218X(00)00322-X. |
[2] | D. Barth and H. Fournier, A degree bound on decomposable trees, Discrete Math. 306 (2006) 469-477, doi: 10.1016/j.disc.2006.01.006. |
[3] | M. Hornák and M. Woźniak, On arbitrarily vertex decomposable trees, Technical report, Faculty of Applied Mathematics, Kraków (2003), submitted. |
[4] | M. Hornák and M. Woźniak, Arbitrarily vertex decomposable trees are of maximum degree at most six, Opuscula Mathematica 23 (2003) 49-62. |
Received 26 January 2005
Revised 5 October 2005
Close