Dually chordal graph

In the mathematical area of graph theory, an undirected graph G is dually chordal if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques is the dual of a hypertree. Originally, these graphs were defined by maximum neighborhood orderings and have a variety of different characterizations. Unlike for chordal graphs, the property of being dually chordal is not hereditary, i.e., induced subgraphs of a dually chordal graph are not necessarily dually chordal (hereditarily dually chordal graphs are exactly the strongly chordal graphs), and a dually chordal graph is in general not a perfect graph.

Dually chordal graphs appeared first under the name HT-graphs.

Dually chordal graphs are the clique graphs of chordal graphs, i.e.,
the intersection graphs of maximal cliques of chordal graphs.

The following properties are equivalent:

The condition on the closed neighborhood hypergraph also implies that a graph is dually chordal if and only if its square is chordal and its closed neighborhood hypergraph has the Helly property.

In De Caria & Gutierrez (2012) dually chordal graphs are characterized in terms of separator properties.
In Bresar (2003) it was shown that dually chordal graphs are precisely the intersection graphs of maximal hypercubes of graphs of acyclic cubical complexes.

The structure and algorithmic use of doubly chordal graphs is given by Moscarini (1993).
These are graphs which are chordal and dually chordal.

Dually chordal graphs can be recognized in linear time, and a maximum neighborhood ordering of a dually chordal graph can be found in linear time.

While some basic problems such as maximum independent set, maximum clique, coloring and clique cover remain NP-complete for dually chordal graphs, some variants of the minimum dominating set problem and Steiner tree are efficiently solvable on dually chordal graphs (but Independent Domination remains NP-complete). See Brandstadt, Chepoi & Dragan (1999) for the use of dually chordal graph
properties for tree spanners, and see Brandstadt, Leitert & Rautenbach (2012) for a linear time algorithm of efficient domination and
efficient edge domination on dually chordal graphs.