On clique-complete graphs (Q1382831)

Let \(G\) be a simple graph. The clique graph \(K(G)\) is the intersection graph of the maximal cliques of \(G\). A vertex in \(G\) is universal if it is adjacent to all other vertices in \(G\). The \(n\)th iterated clique graph of \(G\) is defined by \(K^{(n)}= K(K^{n-1} (G))\) and \(G\) is \(n\)-convergent if \(K^n (G)\) is isomorphic to the one-vertex graph \(K_1\). \(G\) is called clique-complete if \(K^2(G)\simeq K_1\), i.e. a graph is clique-complete iff every two of its maximal cliques intersect. \(G\) is said to be critical if for each induced proper subgraph \(H\) of \(G\), either \(H\) contains an universal vertex, or \(H\) is not clique-complete. Finally a graph \(Q_n= (V,E)\), \(n\geq 3\), is defined in following manner: (1) \(V(Q_n)= \{u_1, u_2,\dots, u_n\}\cup \{v_1, v_2,\dots, v_n\}\); (2) the subgraph of \(Q_n\) induced by \(\{v_1,\dots, v_n\}\) is isomorphic to the complement \(\overline{C}_n\) of the circuit \(C_n\); and (3) for each \(i\) with \(1\leq i\leq n\) holds \(N[u_i]= V(Q_n)- v_i\) for the neighborhood \(N[u_i]\) of \(u_i\). (The figures of the graphs \(\overline{Q}_3\) \(\overline{Q}_5\) are given in the paper.) The main result (Theorem 2) consists in a description of the family of minimal graphs which are clique-complete but have no universal vertices: A graph free of universal vertices is clique-complete and critical iff it is isomorphic to \(Q_{2n+1}\), for some positive integer \(n\). Moreover the authors show that the problem of recognizing clique-complete graphs is Co-NP-complete (Theorem 1). Also they give four additional conclusions, for example, that every clique-complete interval graph contains a universal vertex (Corollary 15).