On the clique operator

DOI10.1007/BFB0054327MaRDI QIDQ3839009zbMATH OpenFDO

Authors M. Gutierrez, João Meidanis

Publication date 8 October 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054327

zbMATH Keywords

clique graphHelly graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (05C99)

Review text

Let \(k(G)\) be the clique graph of a graph \(G\) having as vertices all cliques of \(G\), with two cliques adjacent when they intersect. The authors study the image \(k({\mathcal G})\), where \({\mathcal G}\) denotes the class of all graphs, and the question whether \(k({\mathcal G})\) equals \(k^2({\mathcal G})\) or not. (For a characterization of \(k({\mathcal G})\) see also \textit{F. S. Roberts} and \textit{J. H. Spencer} [J. Comb. Theory, Ser. B 10, 102-108 (1971; Zbl 0215.05801)].) By investigating the structure of graphs in \(k({\mathcal G})\) that are not Helly graphs they show that there are two special subgraphs which have to be present in this situation, and prove that one of these subgraphs belongs also to \(k^2({\mathcal G})\). For the entire collection see [Zbl 0889.00032].

Recommendations

• scientific article; zbMATH DE number 2096439
• The images of the clique operator and its square are different
• scientific article; zbMATH DE number 2096436
• Clique graphs and Helly graphs
• The difference between clique graphs and iterated clique graphs

Cited in

(17)

• The complexity of clique graph recognition
• Clique graphs of packed graphs
• On clique-gated graphs
• A class of clique-closed graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Two infinite families of critical clique-Helly graphs
• The clique operator, set families, and their properties
• The difference between clique graphs and iterated clique graphs
• The images of the clique operator and its square are different
• On replete graphs
• scientific article; zbMATH DE number 2096436 (Why is no real title available?)
• scientific article; zbMATH DE number 2096439 (Why is no real title available?)
• Characterizing clique graphs of chordal comparability graphs
• The Clique Corona Operation and Greedoids
• Intersection graphs and the clique operator
• Clique graphs and Helly graphs
• The clique operator on matching and chessboard graphs

This page was built for publication: On the clique operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3839009)