A note on arbitrarily vertex decomposable graphs

Antoni Marczyk

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.

Mathematics Subject Classification: 05C38, 05C70.

Full text (pdf)