TY  - JOUR
ID  - Marczyk2006
LB  - Marczyk2006
AU  - Marczyk, Antoni
TI  - A note on arbitrarily vertex decomposable graphs
ST  - A note on arbitrarily vertex decomposable graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2006
VL  - 26
IS  - 1
SP  - 109
EP  - 118
DO  - http://dx.doi.org/10.7494/OpMath.2006.26.1.109
UR  - http://dx.doi.org/10.7494/OpMath.2006.26.1.109
AB  - A graph \(G\) of order \(n\) is said to be arbitrarily vertex decomposable if for each sequence \((n_{1},\ldots,n_k)\) of positive integers such that \(n_{1}+\ldots+n_{k}=n\) there exists a partition \((V_{1},\ldots,V_{k})\) of the vertex set of \(G\) such that for each \(i \in \{1,\ldots,k\}\), \(V_{i}\) induces a connected subgraph of \(G\) on \(n_i\) vertices. In this paper we show that if \(G\) is a two-connected graph on \(n\) vertices with the independence number at most \(\lceil n/2\rceil\) and such that the degree sum of any pair of non-adjacent vertices is at least \(n-3\), then \(G\) is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound \(n-3\) is replaced by \(n-2\).
KW  - arbitrarily vertex decomposable graphs
KW  - traceable graphs
KW  - independence number
KW  - perfect matching
SN  - 1232-9274
ER  -