ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 26(2) (2006) 291-305
DOI: 10.7151/dmgt.1321


Sylwia Cichacz,  Agnieszka Görlich,  Antoni Marczyk, Jakub Przybyło

Faculty of Applied Mathematics
AGH University of Science and Technology
Al. Mickiewicza 30, 30-059 Kraków, Poland

Mariusz Woźniak

Institute of Mathematics of Polish Academy of Sciences
(on leave from AGH)


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.


[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