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:

Here are some of our papers on the subject:

Joao Meidanis
Last modified: Mon Nov 13 17:21:25 -02 2017 by JM