On some families of arbitrarily vertex decomposable spiders
Author(s) -
Tomasz Juszczyk,
Irmina A. Zioło
Publication year - 2010
Publication title -
opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2010.30.2.147
Subject(s) - mathematics , vertex (graph theory) , combinatorics , pure mathematics , graph
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom