On self-clique graphs with given clique sizes (Q1971207)

Let \(G\) be a finite simple graph and let the set of all its cliques be denoted by \({\mathfrak K}(G)\). The clique graph \(K(G)\) of \(G\) is the graph whose vertex set is \({\mathfrak K}(G)\) and two vertices are adjacent in \(K(G)\) iff the corresponding cliques have non-empty intersection; \(G\) is said to be self-clique if it is isomorphic to \(K(G)\). As a consequence of a theorem of Harary the following Theorem 1 is given: If \(G\) is a connected graph whose cliques are all of size 2, then \(G\) is self-clique iff \(G\) is a cycle of length at least 4. A given finite sequence of positive integers \((a_1,a_2,\dots, a_m)\) is called clique size sequence of a graph \(G\) if the \(m\) elements in \({\mathfrak K}(G)\) can be arranged in such a way that the \(i\)th element of \({\mathfrak K}(G)\) is of size \(a_i\), \(i= 1,2,\dots, m\). The result of the present paper is the characterization of all connected self-clique graphs with the clique size sequence \((2,\dots, 2,n)\) where \(n\geq 3\). For this purpose the author constructs two families \({\mathfrak G}_{r,s}\) and \({\mathfrak H}_{t,q}\) of graphs of the clique size sequence mentioned above with integers \(r\geq 0\), \(s\geq 1\), \(t\geq 0\), \(q\geq 0\) such that \(2r+ s= n\), \(2t+ q= n-1\), respectively, by applying certain graph-theoretical operations on a complete graph \(K_n\) on \(n\) vertices. This is also demonstrated by six figures. By an extensive proof the author gets the following result (Theorem 2): Let \(G\) be a connected graph whose clique size sequence is \((2,\dots, 2,n)\), \(n\geq 3\). Then \(G\) is self-clique iff \(G\in{\mathfrak G}_{r,s}\cup{\mathfrak H}_{t,q}\).