Constructible graph

Constructible graph --- конструируемый граф.

Graph [math]\displaystyle{ G }[/math] is constructible if it can be built vertex-by-vertex so that a vertex [math]\displaystyle{ x }[/math] can be added to the currently constructed induced subgraph [math]\displaystyle{ G_{x} }[/math] of [math]\displaystyle{ G }[/math] if there exists a vertex [math]\displaystyle{ y }[/math] of [math]\displaystyle{ G_{x} }[/math] which is adjacent in [math]\displaystyle{ G }[/math] to [math]\displaystyle{ x }[/math] and to all neighbors of [math]\displaystyle{ x }[/math] belonging to [math]\displaystyle{ G_{x} }[/math].

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

See

• also Dismantlable graph.