ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 26(2) (2006)
Faculty of Applied Mathematics
AGH University of Science and Technology
Al. Mickiewicza 30, 30-059 Kraków, Poland
Institute of Mathematics of Polish Academy of Sciences
(on leave from AGH)
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.
Received 26 January 2005
Revised 5 October 2005