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.
- 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
- Received: 2007-10-10.
- Revised: 2009-11-18.
- Accepted: 2010-01-04.
