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.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.