On Clique-Complete Graphs

A graph is {\em clique-complete} if no two of its maximal cliques are disjoint. A vertex is {\em universal} if it is adjacent to all other vertices in the graph. We prove that every clique-complete graph either contains a universal vertex or an induced subgraph in an indexed family ${\cal Q} := \{ Q_{2n + 1}: n \geq 1 \}$, defined in the text. We show that this is precisely the family of minimal graphs which are clique-complete but have no universal vertices. The minimality used here refers to induced subgraphs. \par For $n \geq 2$, we show that $Q_{2n + 1}$ is neither perfect nor planar. It follows that every planar clique-complete graph without a universal vertex contains an induced subgraph isomorphic to $Q_3$. A similar result holds for perfect clique-complete graphs without universal vertices. We also specialize the latter result for certain classes of perfect graphs.

1992