# 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 (2006)

- Volume: 26, Issue: 2, page 291-305
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSylwia Cichacz, et al. "Arbitrarily vertex decomposable caterpillars with four or five leaves." Discussiones Mathematicae Graph Theory 26.2 (2006): 291-305. <http://eudml.org/doc/270575>.

@article{SylwiaCichacz2006,

abstract = {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, $V_i$ induces a connected subgraph of G on $a_i$ 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.},

author = {Sylwia Cichacz, Agnieszka Görlich, Antoni Marczyk, Jakub Przybyło, Mariusz Woźniak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {arbitrarily vertex decomposable graphs; trees; caterpillars; star-like trees; trees, caterpillars},

language = {eng},

number = {2},

pages = {291-305},

title = {Arbitrarily vertex decomposable caterpillars with four or five leaves},

url = {http://eudml.org/doc/270575},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Sylwia Cichacz

AU - Agnieszka Görlich

AU - Antoni Marczyk

AU - Jakub Przybyło

AU - Mariusz Woźniak

TI - Arbitrarily vertex decomposable caterpillars with four or five leaves

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 2

SP - 291

EP - 305

AB - 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, $V_i$ induces a connected subgraph of G on $a_i$ 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.

LA - eng

KW - arbitrarily vertex decomposable graphs; trees; caterpillars; star-like trees; trees, caterpillars

UR - http://eudml.org/doc/270575

ER -

## References

top- [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. Zbl1002.68107
- [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. Zbl1092.05054
- [3] M. Hornák and M. Woźniak, On arbitrarily vertex decomposable trees, Technical report, Faculty of Applied Mathematics, Kraków (2003), submitted. Zbl1132.05048
- [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. Zbl1093.05510

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.