Дважды хордальный граф

Дважды хордальный граф (Doubly chordal graph) — Пусть [math]\displaystyle{ N[v] }[/math] — замкнутая окрестность вершины [math]\displaystyle{ v }[/math]. Вершина [math]\displaystyle{ u \in N[v] }[/math] называется максимальным соседом вершины [math]\displaystyle{ v }[/math], если для всех [math]\displaystyle{ w \in N[v] }[/math] имеет место включение [math]\displaystyle{ N[w] \subseteq N[u] }[/math] (заметим, что [math]\displaystyle{ u = v }[/math] не исключается). Вершина [math]\displaystyle{ v }[/math] называется дважды симплициальной (doubly simplicial),если она симплициальна (т.е. для нее [math]\displaystyle{ N[v] }[/math] — клика) и имеет максимального соседа. Упорядочение [math]\displaystyle{ (v_{1}, \ldots, v_{n}) }[/math]называется дважды совершенным упорядочением (doubly perfect ordering), если каждая вершина [math]\displaystyle{ v_{i} }[/math] дважды симплициальна в [math]\displaystyle{ G_{i} }[/math]. Граф называется дважды хордальным, если он допускает дважды совершенное упорядочение.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. — Новосибирск: Наука. Сиб. отд-ние, 1998.