Arbitrarily vertex decomposable caterpillars with four or five leaves
Sylwia Cichacz ; Agnieszka Görlich ; Antoni Marczyk ; Jakub Przybyło ; Mariusz Woźniak
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 291-305 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) 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.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270575 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1321,
     author = {Sylwia Cichacz and Agnieszka G\"orlich and Antoni Marczyk and Jakub Przyby\l o and Mariusz Wo\'zniak},
     title = {Arbitrarily vertex decomposable caterpillars with four or five leaves},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {291-305},
     zbl = {1142.05065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1321}
}

Sylwia Cichacz; Agnieszka Görlich; Antoni Marczyk; Jakub Przybyło; Mariusz Woźniak. Arbitrarily vertex decomposable caterpillars with four or five leaves. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 291-305. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1321/

[000] [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. | Zbl 1002.68107

[001] [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. | Zbl 1092.05054

[002] [3] M. Hornák and M. Woźniak, On arbitrarily vertex decomposable trees, Technical report, Faculty of Applied Mathematics, Kraków (2003), submitted. | Zbl 1132.05048

[003] [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. | Zbl 1093.05510