Chain graph

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

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

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

N(\pi(1)) \subseteq N(\pi(2)) \subseteq \cdots \subseteq
N(\pi(|P|)).

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

Литература

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