Clique Graph Characterizations of Strongly Chordal Graphs

Abstract

Define an edge $Q_1{Q}_2$ or a triangle $Q_1{Q}_2{Q}_3$ of a clique graph $K(G)$ to be weight-$k$ if $|Q_1\cap Q_2|\ge k$ or $|Q_1\cap Q_2\cap Q_3|\ge k$, respectively. A graph $G$ is shown to be strongly chordal if and only if, for every $k\ge 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.