# zbMATH — the first resource for mathematics

A hierarchy of self-clique graphs. (English) Zbl 1042.05073
Summary: The clique graph $$K(G)$$ of $$G$$ is the intersection graph of all its (maximal) cliques. A connected graph $$G$$ is self-clique whenever $$G \cong K(G)$$. Self-clique graphs have been studied in several papers. Here we propose a hierarchy of self-clique graphs: Type 3 $$\subsetneq$$ Type 2 $$\subsetneq$$ Type 1 $$\subsetneq$$ Type 0. We give characterizations for classes of Types 3, 2 and 1 (including Helly self-clique graphs) and several new constructions of families of self-clique graphs. It is shown that all (but one) previously published examples of self-clique graphs are of Type 2. Our methods provide a unified approach and generalizations of those examples. As further applications, we give a characterization of the self-clique graphs such that at most 3 cliques have more than two vertices (they are all of Type 2) and a description of the diamond-free graphs of Type 2.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
GAP
Full Text:
##### References:
  Balakrishnan, R; Paulraja, P, Self-clique graphs and diameters of iterated clique graphs, Utilitas math., 29, 263-268, (1986) · Zbl 0614.05053  Balconi, G, Caratterizzazione matriciale dei grafi autoduali, Istit. lombardo accad. sci. lett. rend. A, 113, 360-365, (1979) · Zbl 0456.05043  Bondy, A; Durán, G; Lin, M.C; Szwarcfiter, J.L, A sufficient condition for self-clique graphs, Electron. notes discrete math., 7, 19-23, (2001)  Chia, G.L, On self-clique graphs with given clique sizes, Discrete math., 212, 185-189, (2000) · Zbl 0945.05050  Escalante, F, Über iterierte clique-graphen, Abh. math. sem. univ. Hamburg, 39, 58-68, (1973) · Zbl 0266.05116  The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.3 (2002) (http://www.gap-system.org).  George, J.C; Porter, T.D; Wallis, W.D, Characterizing balanced bipartite graphs with part-switching automorphisms, Bull. inst. combin. appl., 28, 85-88, (2000) · Zbl 0946.05073  Hamelink, R.C, A partial characterization of clique graphs, J. combin. theory, 5, 192-197, (1968) · Zbl 0167.22203  Hedman, B, Diameters of iterated clique graphs, Hadronic J., 9, 273-276, (1986) · Zbl 0644.05032  Larrión, F; Neumann-Lara, V, A family of clique divergent graphs with linear growth, Graphs combin., 13, 263-266, (1997) · Zbl 0892.05041  Larrión, F; Neumann-Lara, V, On clique-divergent graphs with linear growth, Discrete math., 245, 139-153, (2002) · Zbl 0993.05143  F. Larrión, V. Neumann-Lara, M.A. Pizaña, Clique divergent clockwork graphs and partial orders, Discrete Appl. Math., to appear.  Lim, C.K; Peng, Y.H, On graphs without multicliqual edges, J. graph theory, 5, 443-451, (1981) · Zbl 0492.05056  V. Neumann-Lara, On clique-divergent graphs, in: Problèmes Combinatoires et Théorie des Graphes, Colloques Internationaux CNRS, Vol. 260, CNRS, Paris, 1978. · Zbl 0413.05058  Roberts, F.S; Spencer, J.H, A characterization of clique graphs, J. combin. theory ser. B, 10, 102-108, (1971) · Zbl 0215.05801  Szwarcfiter, J.L, Recognizing clique-Helly graphs, Ars combin., 45, 29-32, (1997) · Zbl 0933.05127  J.L. Szwarcfiter, A survey on clique graphs. in: C. Linhares-Sales, B.A. Reed (Eds.), Recent Advances in Algorithms and Combinatorics, CMS Books Math./Ouvrages Math. SMC, Vol. 11, Springer, New York, 2003, pp. 109-136 · Zbl 1027.05071  Wallis, W.D; Wu, J.L, Squares, clique graphs and chordality, J. graph theory, 20, 37-45, (1995) · Zbl 0832.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.