Research work · 1998
Dually Chordal Graphs
Andreas Brandstädt, Feodor F. Dragan, Victor D. Chepoi, Vitaly Voloshin
SIAM Journal on Discrete Mathematics
Abstract
Recently in several papers, graphs with maximum neighborhood orderings were characterized and turned out to be algorithmically useful. This paper gives a unified framework for characterizations of those graphs in terms of neighborhood and clique hypergraphs which have the Helly property and whose line graph is chordal. These graphs are dual (in the sense of hypergraphs) to chordal graphs. By using the hypergraph approach in a systematical way new results are obtained, some of the old results are generalized, and some of the proofs are simplified.