An inequality characterizing chordal graphs (Q2761050)

A graph is chordal if every cycle of length at least four has a chord. A new characterization of chordal graphs is given, as graphs that satisfy equality in the inequality \(\sum_Q(1-\text{comp} N(Q))\leq \text{comp} G\), where the sum is taken over all nonempty complete subgraphs \(Q\), \(N(Q)\) denotes the set of vertices adjacent to all vertices of \(Q\) and \(\text{comp} G\) denotes the number of connected components of \(G\). The inequality is also established. The concept is extended to more general graph parameters and it is shown, e.g., that \(\sum_Q(1-\gamma (N(Q)))\leq \gamma (G)\) (where \(\gamma \) denotes the dominating number) holds for any graph \(G\), while equality holds exactly for \(P_4\)-free chordal graphs.