Dismantlable graph

Dismantlable graph --- разборный граф.

A graph [math]\displaystyle{ G }[/math] is said to be dismantlable if its vertices can be removed one after another in such a way that a vertex [math]\displaystyle{ x }[/math] can be taken off the currently remaining subgraph [math]\displaystyle{ G_{x} }[/math] of [math]\displaystyle{ G }[/math] if there exists a vertex [math]\displaystyle{ y }[/math] in [math]\displaystyle{ G_{x} }[/math] which is adjacent to [math]\displaystyle{ x }[/math] and to all neighbors of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ G_{x} }[/math].

A graph [math]\displaystyle{ G }[/math] is said to be dismantlable if there is a well-order [math]\displaystyle{ \preceq }[/math] on [math]\displaystyle{ V(G) }[/math] such that every vertex [math]\displaystyle{ x }[/math] which is not the greatest element of [math]\displaystyle{ (V(G), \preceq) }[/math], if such a greatest element exists, is dominated by some vertex [math]\displaystyle{ y \neq x }[/math] in a subgraph of [math]\displaystyle{ G }[/math] induced by the set [math]\displaystyle{ \{z \in V(G): x \preceq z\} }[/math]. The well-order [math]\displaystyle{ \preceq }[/math] on [math]\displaystyle{ V(G) }[/math], and the enumeration of the vertices of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ \preceq }[/math], will be called a dismantling order and a dismantling enumeration, respectively.

See also

• Constructible graph.