Clique graphs and Helly graphs (Q802632): Difference between revisions

The clique graph K(G) of a graph G is the intersection graph of the cliques of G. Clique graphs have been characterized by \textit{F. S. Roberts} and \textit{J. Spencer} [J. Comb. Theory, Ser. B 10, 102-108 (1971; Zbl 0245.05128)]. This characterization was motivated by the sufficient condition of \textit{R. C. Hamelink} [J. Comb. Theory 5, 192-197 (1968; Zbl 0167.222)]: the set of cliques of G enjoys the Helly property - that is, every set of pairwise intersecting cliques has a nonempty intersection. Such a graph is called a clique-Helly graph. \textit{F. Escalante} [Abh. Math. Semin. Univ. Hamb. 39, 59-68 (1973; Zbl 0266.05116)] has shown that the class of clique-Helly graphs is closed under the clique graph operator K, i.e., the clique graph of a clique-Helly graph is again a clique-Helly graph and every clique-Helly graph is the clique graph of some clique-Helly graph. \textit{Lim Chong-Keang} and \textit{Peng Yee-Hock} [J. Graph Theory 5, 443-451 (1981; Zbl 0492.05056)] showed that the class of graphs without multicliqual edges is a proper subclass fixed under K and \textit{B. Hedman} [J. Comb. Theory, Ser. B 37, 270-278 (1984; Zbl 0537.05057)] showed that the class of indifference graphs converge, under repeated application of the operator K, to the one-vertex graph. The authors characterize those graphs that converge, under repeated application of K, to the one-vertex graph and exhibit a number of classes of graphs fixed under K.