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.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI
[1] Balakrishnan, R; Paulraja, P, Self-clique graphs and diameters of iterated clique graphs, Utilitas math., 29, 263-268, (1986) · Zbl 0614.05053
[2] Balconi, G, Caratterizzazione matriciale dei grafi autoduali, Istit. lombardo accad. sci. lett. rend. A, 113, 360-365, (1979) · Zbl 0456.05043
[3] 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)
[4] Chia, G.L, On self-clique graphs with given clique sizes, Discrete math., 212, 185-189, (2000) · Zbl 0945.05050
[5] Escalante, F, Über iterierte clique-graphen, Abh. math. sem. univ. Hamburg, 39, 58-68, (1973) · Zbl 0266.05116
[6] The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.3 (2002) (http://www.gap-system.org).
[7] 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
[8] Hamelink, R.C, A partial characterization of clique graphs, J. combin. theory, 5, 192-197, (1968) · Zbl 0167.22203
[9] Hedman, B, Diameters of iterated clique graphs, Hadronic J., 9, 273-276, (1986) · Zbl 0644.05032
[10] Larrión, F; Neumann-Lara, V, A family of clique divergent graphs with linear growth, Graphs combin., 13, 263-266, (1997) · Zbl 0892.05041
[11] Larrión, F; Neumann-Lara, V, On clique-divergent graphs with linear growth, Discrete math., 245, 139-153, (2002) · Zbl 0993.05143
[12] F. Larrión, V. Neumann-Lara, M.A. Pizaña, Clique divergent clockwork graphs and partial orders, Discrete Appl. Math., to appear.
[13] Lim, C.K; Peng, Y.H, On graphs without multicliqual edges, J. graph theory, 5, 443-451, (1981) · Zbl 0492.05056
[14] 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
[15] Roberts, F.S; Spencer, J.H, A characterization of clique graphs, J. combin. theory ser. B, 10, 102-108, (1971) · Zbl 0215.05801
[16] Szwarcfiter, J.L, Recognizing clique-Helly graphs, Ars combin., 45, 29-32, (1997) · Zbl 0933.05127
[17] 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
[18] 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.