On minimal vertex separators of dually chordal graphs: properties and characterizations (Q1759837): Difference between revisions

A chord of a cycle is an edge joining two nonconsecutive vertices of the cycle. Chordal graphs are those without chordless cycles of length at least four. A vertex \(w\) is a maximum neighbor of \(v\) if \(N^2[v] \subset N[w]\). A linear ordering \(v_1,\dots,v_n\) of the vertices of \(G\) is a maximum neighborhood ordering of \(G\), if for \(i=1,\dots ,n\), \(v_i\) has a maximum neighbor in \(G[\{v_i,\dots ,v_n\}]\). Dually chordal graphs can be defined as those possessing a maximum neighborhood ordering. In this paper, two major characterizations of dually chordal graphs are given. Their first result states that a graph is dually chordal if and only if it possesses a spanning tree such that every minimal vertex separator induces a subtree. Their second result states that a graph is dually chordal if and only if the family of minimal vertex separator is Helly, its intersection graph is chordal and each of its members induces a connected subgraph.