Dually chordal graph

Dually chordal graph --- двойственно-хордальный граф.

A vertex [math]\displaystyle{ u \in N[v] }[/math] ([math]\displaystyle{ N[v] }[/math] is a closed neighborhood of [math]\displaystyle{ v }[/math]) is a maximum neighbor of [math]\displaystyle{ v }[/math] if for all [math]\displaystyle{ w \in N[v] }[/math], [math]\displaystyle{ N[w] \subseteq N[u] }[/math] holds (note that [math]\displaystyle{ u = v }[/math] is not excluded). A linear ordering [math]\displaystyle{ (v_{1}, \ldots, v_{n}) }[/math] of [math]\displaystyle{ V }[/math] is a maximum neighborhood ordering of [math]\displaystyle{ G }[/math] if for all [math]\displaystyle{ i \in \{1, \ldots, n\} }[/math], there is a maximum neighbor [math]\displaystyle{ u_{i} \in N_{i}[v_{i}] }[/math]; i.e.,

[math]\displaystyle{ \mbox{for all }w \in N_{i}[u_{i}], \; N_{i}[w] \subseteq N_{i}[u_{i}]\mbox{ holds}. }[/math]

The graphs with maximum neighborhood ordering are dual to chordal graphs and called dually chordal graph.

The [math]\displaystyle{ k }[/math]-th power [math]\displaystyle{ G^{k} }[/math], [math]\displaystyle{ k \geq 1 }[/math], of [math]\displaystyle{ G }[/math] has the same vertices as [math]\displaystyle{ G }[/math], and two distinct vertices are joined by an edge in [math]\displaystyle{ G^{k} }[/math] if and only if their distance in [math]\displaystyle{ G }[/math] is at most [math]\displaystyle{ k }[/math]. It is known that any power of a dually chordal graph is dually chordal.