Arbitrarily vertex decomposable caterpillars with four or five leaves

• Autorzy: Sylwia Cichacz , Agnieszka Görlich , Antoni Marczyk , Jakub Przybyło , Mariusz Woźniak
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2006
• Tom: 26
• Numer: 2
• Strony: 291-305

Daty

wydano

2006

otrzymano

2005-01-26

poprawiono

2005-10-05

Twórcy

autor

Sylwia Cichacz

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

autor

Agnieszka Görlich

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

autor

Antoni Marczyk

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

autor

Jakub Przybyło

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

autor

Mariusz Woźniak

• Institute of Mathematics of Polish Academy of Sciences

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1321