×

zbMATH — the first resource for mathematics

Clique graphs and Helly graphs. (English) Zbl 0726.05060
The clique graph K(G) of a graph G is the intersection graph of the cliques of G. Clique graphs have been characterized by F. S. Roberts and J. Spencer [J. Comb. Theory, Ser. B 10, 102-108 (1971; Zbl 0245.05128)]. This characterization was motivated by the sufficient condition of 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. 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. Lim Chong-Keang and 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 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.

MSC:
05C99 Graph theory
05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstee, R.P; Farber, M, Characterizations of totally balanced matrices, J. algorithms, 5, 215-230, (1984) · Zbl 0551.05026
[2] Anstee, R.P; Farber, M, On bridged graphs and cop-win graphs, J. combin. theory ser. B, 44, 22-28, (1988) · Zbl 0654.05049
[3] Balakrishnan, R; Paulraja, P, Self-clique graphs and diameters of iterated clique graphs, Utilitas math., 29, 263-268, (1986) · Zbl 0614.05053
[4] Bandelt, H.-J; Mulder, H.M, Distance-hereditary graphs, J. combin. theory ser. B, 41, 182-208, (1986) · Zbl 0605.05024
[5] Bandelt, H.-J; Pesch, E, Dismantling absolute retracts of reflexive graphs, European J. combin., 10, 211-220, (1989) · Zbl 0674.05065
[6] Berge, C, ()
[7] Chong-Keang, L; Yee-Hock, P, On graphs without multicliqual edges, J. graph theory, 5, 443-451, (1981) · Zbl 0492.05056
[8] D’Atri, A; Moscarini, M, Recognition algorithms and design methodology for acyclic database schemes, (), 43-67
[9] D’Atri, A; Moscarini, M, On hypergraph acyclicity and graph chordality, Report IASI-CNR R. 170, (1986) · Zbl 0662.68111
[10] Duchet, P, Propriété de Helly et problèmes de représentation, (), 117-118, Paris · Zbl 0413.05042
[11] Duchet, P, Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs, Ann. discrete math., 21, 67-96, (1984)
[12] Duke, R, Types of cycles in hypergraphs, Ann. discrete math., 27, 399-418, (1985)
[13] Escalante, F, Über iterierte clique-graphen, Abh. math. sem. univ. Hamburg, 39, 59-68, (1973) · Zbl 0266.05116
[14] Escalante, F; Toft, B, On clique-critical graphs, J. combin. theory ser. B, 17, 170-182, (1974) · Zbl 0288.05126
[15] Farber, M, Characterizations of strongly chordal graphs, Discrete math., 43, 173-189, (1983) · Zbl 0514.05048
[16] Farber, M; Jamison, R.E, Convexity in graphs and hypergraphs, SIAM J. algebraic discrete methods, 7, 433-444, (1986) · Zbl 0591.05056
[17] Gavril, F, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[18] Hamelink, R, A partial characterization of clique graphs, J. combin. theory, 5, 192-197, (1968) · Zbl 0167.22203
[19] Hedetniemi, S.T; Slater, P.J, Line graphs of triangleless graphs and iterated clique graphs, (), 139-147 · Zbl 0255.05121
[20] Hedman, B, Clique graphs of time graphs, J. combin. theory ser. B, 27, 270-278, (1984) · Zbl 0547.05056
[21] Howorka, E, On metric properties of certain clique graphs, J. combin. theory ser. B, 27, 67-74, (1979) · Zbl 0337.05138
[22] Howorka, E, A characterization of ptolemaic graphs, J. graph theory, 5, 323-331, (1981) · Zbl 0437.05046
[23] Jawhari, E.M; Misane, D; Pouzet, M, Retracts: graphs and ordered sets from the metric point of view, (), 175-226
[24] Lim, C.-K, A result on iterated clique graphs, J. austral. math. soc. ser. A, 32, 289-294, (1982) · Zbl 0492.05057
[25] Monma, C.L; Wei, V.K, Intersection graphs of paths in a tree, J. combin. theory ser. B, 41, 141-181, (1986) · Zbl 0595.05062
[26] Neumann-Lara, V, On clique-divergent graphs, (), 313-315, Paris
[27] Neumann-Lara, V, Clique divergence in graphs, (), 563-569, Szeged · Zbl 0524.05050
[28] Nowakowski, R; Rival, I, The smallest graph variety containing all paths, Discrete math., 43, 223-234, (1983) · Zbl 0511.05059
[29] Nowakowski, R; Winkler, P, Vertex-to-vertex pursuit in a graph, Discrete math., 43, 235-239, (1983) · Zbl 0508.05058
[30] Pesch, E, ()
[31] Peyrat, C; Rall, D.F; Slater, P.J, On iterated clique graphs with increasing diameters, J. graph theory, 10, 167-171, (1986) · Zbl 0596.05036
[32] Poston, T, Fuzzy geometry, () · Zbl 0732.53002
[33] Quilliot, A, Homomorphismes, points fixes, rétractions et jeux de poursuite dans LES graphes, LES ensembles ordonnés et LES espaces métriques, Thèse de doctorat d’etat, (1983), Paris
[34] Quilliot, A, On the Helly property working as a compactness criterion on graphs, J. combin. theory ser. A, 40, 186-193, (1985) · Zbl 0575.05026
[35] Roberts, F.S; Spencer, J.H, A characterization of clique graphs, J. combin. theory ser. B, 10, 102-108, (1971) · Zbl 0215.05801
[36] Soltan, V.P, d-convexity in graphs, Soviet math. dokl., 28, 419-421, (1983) · Zbl 0553.05060
[37] Soltan, V.P; Čepoj, V.D, Uslovija sochranenija v grafe d-vypuklost’ju diametrov množestv, Kibernetika, No. 6, 14-18, (1983)
[38] Acharya, B.D, Some queries on the periodicity and convergence of a graph, (), 185-205
[39] Balconi, G, Singrammi con duale vertici-cricche, Rend. istit. lomb. A, 110, 117-124, (1976) · Zbl 0381.05047
[40] Balconi, G, Quadrati di singrammi e polarità, Rend. istit. lomb. A, 112, 24-30, (1978) · Zbl 0421.05061
[41] Carnazolla, G, Grafi di cricche iterati, Ph.D. thesis, (1983/1984)
[42] Chen, B.-L; Lih, K.-W, Diameters of iterated clique graphs of chordal graphs, J. graph theory, 14, 391-396, (1990) · Zbl 0726.05059
[43] Prisner, E, Homology and convergence of iterated clique graphs, (1988), preprint
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.