The Clique Operator

Given a simple, undirected graph G the clique operator K constructs K(G), the intersection graph of G's maximal cliques. Our goal is to study the properties of this operator. We are especially interested in what happens when you apply the operator iteratively, that is, compute K(G), then K(K(G)), and so on.

Compared to other operators that act on graphs, such as the ones that construct the line graph or the block graph, K is much richer. For instance, if you apply the line operator iteratively, no matter which graph you begin with, you end up alternating between two graphs. A similar phenomenon occurs with the block operator. However, for K it is possible to have a divergent sequence of graphs (graphs that grow more and more), or to alternate among any number of graphs.

My colleague Marisa Gutierrez, from the National University at La Plata, Argentina, is my most frequent collaborator in this field.

Here are some open questions of interest:

• Find a polynomial time algorithm that recognizes the image of K.
• Determine the largest clique-fixed class of graphs. A class C is clique-fixed when K(C) = C.
• Is it true that the image of K is the same as the image of K^2 (the second iterate of K)?
• Does K have the computational power of Turing machines? In other words, is it possible to code an arbitrary algorithm and its input as a graph, and simulate the algorithm steps by iterated application of K?

Here are some of our papers on the subject:

• M.Gutierrez and J. Meidanis. Algebraic Theory for the Clique Operator. Journal of the Brazilian Computing Society, 7, (3), 2001. DOI reference. A working draft follows. Download ps
• M.Gutierrez and J. Meidanis. Recognizing Clique Graphs of Directed Edge Path Graphs. Discrete Applied Mathematics, 126 (2-3), pp. 297-304, March 2003. DOI reference. A working draft follows. Download ps
• M.Gutierrez and J. Meidanis. On Clique Graph Recognition. Ars Combinatoria, 63 (2002) pp. 207-210. In this paper we reduce the problem of recognizing clique graphs to graphs of diameter at most 2. A working draft follows. Download ps
• M.Gutierrez and J. Meidanis. The Clique Operator, Set Families, and Their Properties. Brazilian Symposium on Graphs and Combinatorics (GRACO), Ceará, Electronic Notes on Discrete Mathematics (Jayme Szwarcfiter and Siang W. Song, eds.), vol. 7, Elsevier Science Publishers, 2001. A 3-page summary follows. Download ps
• M.Gutierrez and J. Meidanis. On the Clique Operator. Latin American Theoretical Informatics (LATIN), Campinas, Brazil Lecture Notes in Computer Science (Claudio L. Lucchesi and Arnaldo V. Moura, eds.), vol. 1380, Springer, 1998. Springer link Download pdf (early version)