Arbitrarily vertex decomposable graph

Arbitrarily vertex decomposable graph — произвольно вершинно разложимый граф.

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.

See also

• Admissible sequence.