Admissible sequence

Материал из WikiGrapp
Перейти к:навигация, поиск

Admissible sequenceдопустимая последовательность.

Let \,G = (V,E) be a simple undirected graph of order \,n. Let \tau - (n_{1}, \ldots, n_{k}) denote a sequence of positive integers such that n_{1} + \ldots + n_{k} = n. Such a sequence will be called admissible for \,G. If \tau = (n_{1}, \ldots, n_{K}) is an admissible sequence for \,G and there exists a partition (V_{1},
\ldots, V_{k}) of the vertex set \,V such that for each i \in \{1, \ldots, k\}, \,|V_{i}| = n_{i} and the subgraph induced by \,V_{i} is connected, then \,\tau is called realizable in \,G and the sequence (V_{1}, \ldots, V_{k}) is said to be \,G-realization of \,\tau or a realization of \,\tau in \,G. A graph \,G is arbitrarily vertex decomposable if for each admissible sequence \,\tau for \,G there exists a \,G-realization of \,\tau.