Chain graph

Chain graph — цепной граф.

A bipartite graph [math]\displaystyle{ \,G = (P,Q,E) }[/math] is called a chain graph if there is an ordering [math]\displaystyle{ \,\pi }[/math] of the vertices in [math]\displaystyle{ \,P }[/math], [math]\displaystyle{ \pi: \; \{1, \ldots, |P|\} \rightarrow P }[/math], such that

[math]\displaystyle{ N(\pi(1)) \subseteq N(\pi(2)) \subseteq \cdots \subseteq N(\pi(|P|)). }[/math]

Here [math]\displaystyle{ \,N(v) }[/math] is a neighborhood of [math]\displaystyle{ \,v }[/math]. It is known that [math]\displaystyle{ \,G }[/math] is a chain graph iff it does not contain an independent pair of edges (an induced [math]\displaystyle{ \,2K_{2} }[/math]).

Литература

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