Opuscula Math.
26
, no. 1
(), 109-118
Opuscula Mathematica

# A note on arbitrarily vertex decomposable graphs

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.