Arbitrarily vertex decomposable graph

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

A graph [math]\displaystyle{ \,G }[/math] of order [math]\displaystyle{ \,n }[/math] is said to be arbitrarily vertex decomposable, if for each sequence [math]\displaystyle{ (n_{1}, \ldots, n_{k}) }[/math] of positive integers such that [math]\displaystyle{ n_{1} + \ldots + n_{k} = n }[/math] there exists a partition [math]\displaystyle{ (V_{1}, \ldots, V_{k}) }[/math] of the vertex set of [math]\displaystyle{ \,G }[/math] such that, for each [math]\displaystyle{ i \in \{1, \ldots, k\} }[/math], [math]\displaystyle{ V_{i} }[/math] induces a connected subgraph of [math]\displaystyle{ \,G }[/math] on [math]\displaystyle{ \,n_{i} }[/math] vertices.

See also

• Admissible sequence.