Strongly Chordal Graphs and Related Structures

Abstract

Strongly chordal graphs were introduced by Farber in 1983, as a restricted class of graphs for which the weighted dominating set problem can be solved in polynomial time; the problem is NP-hard for chordal graphs in general.  Farber and others explored graph, hypergraph, and matrix characterizations of strongly chordal graphs.  We present a new proof of the forbidden subgraph characterization of strongly chordal graphs, from which other characterizations follow.  The key is that the hypergraph setting is more natural for parts of the proof.

No background knowledge will be assumed.