Opuscula Math. 30, no. 2 (2010), 147-154
http://dx.doi.org/10.7494/OpMath.2010.30.2.147

Opuscula Mathematica

# On some families of arbitrarily vertex decomposable spiders

Tomasz Juszczyk
Irmina A. Zioło

Abstract. A graph $$G$$ of order $$n$$ is called arbitrarily vertex decomposable if for each sequence $$(n_1, ..., n_k)$$ of positive integers such that $$\sum _{i=1}^{k} n_i = n$$, there exists a partition $$(V_1, ..., V_k)$$ of the vertex set of $$G$$ such that for every $$i \in \{1, ...., k\}$$ the set $$V_i$$ induces a connected subgraph of $$G$$ on $$n_i$$ vertices. A spider is a tree with one vertex of degree at least $$3$$. We characterize two families of arbitrarily vertex decomposable spiders which are homeomorphic to stars with at most four hanging edges.

Keywords: arbitrarily vertex decomposable graph, trees.

Mathematics Subject Classification: 05C05, 05C35.

Full text (pdf)

• Tomasz Juszczyk
• AGH University of Science and Technology, Faculty of Electrical Engineering, Automatics, Computer Science and Electronics, al. Mickiewicza 30, 30-059 Kraków, Poland
• Irmina A. Zioło
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland
• Revised: 2009-11-18.
• Accepted: 2010-01-04.