@Article{Marczyk2006,
author = "Marczyk, Antoni",
title = "A note on arbitrarily vertex decomposable graphs",
journal = "Opuscula Math.",
year = "2006",
volume = "26",
number = "1",
pages = "109--118",
doi = "http://dx.doi.org/10.7494/OpMath.2006.26.1.109",
url = "http://dx.doi.org/10.7494/OpMath.2006.26.1.109",
abstract = "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\).",
keywords = "arbitrarily vertex decomposable graphs, traceable graphs, independence number, perfect matching",
issn = "1232-9274"
}