Clique tree generalization and new subclasses of chordal graphs

The notion of a clique tree plays a central role in obtaining an intersection graph representation of a chordal graph. In this paper, we introduce a new structure called the reduced clique hypergraph of a chordal graph. Unlike a clique tree, the reduced clique hypergraph is a unique structure associated with a chordal graph. We show that all clique trees of a chordal graph can be obtained from the reduced clique hypergraph; thus the reduced clique hypergraph can be thought of as a generalization of the notion of a clique tree. We then link the reduced clique hypergraph notion to minimal vertex separators of chordal graph by proving a structure theorem which shows that the edges of the reduced clique hypergraph are in one-one correspondence with the minimal vertex separators. We also show that a closed-form formula for the number of clique trees of a chordal graph can be derived using these results. Using an algorithmic characterization of minimal vertex separators, we obtain efficient algorithms to compute the reduced clique hypergraph and to count the number of clique trees of a chordal graph. Finally, guided by the reduced clique hypergraph structure we propose a few new subclasses of chordal graphs and relate them to each other and the existing subclasses. © 2002 Elsevier Science B.V.