Clique Graph Characterizations of Strongly Chordal Graphs

Abstract

Define an edge \( Q_1Q_2 \) or a triangle \( Q_1Q_2Q_3 \) of a clique graph \( K(G) \) to be weight-\( k \) if \( |Q_1 \cap Q_2| \geq k \) or \( |Q_1 \cap Q_2 \cap Q_3| \geq k \), respectively. A graph \( G \) is shown to be strongly chordal if and only if, for every \( k \geq 1 \), every cycle of weight-\( k \) edges in \( K(G) \) either has a weight-\( k \) chord or is a weight-\( k \) triangle—this mimics the usual definition of chordal graphs. Similarly, trivially perfect graphs have a characterization that mimics a simple characterization of component-complete graphs.