DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 291-305
DOI: 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
AGH University of Science and Technology
Al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: marczyk@uci.agh.edu.pl

Mariusz Woźniak

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

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