The family of octahedral graphs and the clique operator

PABLO DE CARIA

Huatulco

Congreso; International Workshop Combinatorial and Computational Aspects of Optimization, Topology and Algebra; 2012

Centro de Investigación y de Estudios Avanzados del IPN

Given a simple graph G, a set C ⊆ V(G) is a clique if its vertices are pairwise adjacent and C is maximal in this sense. The clique graph of G has all the cliques of G as vertices and two of them are adjacent if and only if their intersection is not empty. Let J denote the class of all graphs. The clique operator is the function K: G → G that assigns to each graph its clique graph. The exponential notation K^n will indicate the composition of the clique operator with itself n times.Define the n-dimensional octahedron O_n, n ≥ 3, as the graph such that V(O_n) = {1, 2, ..., 2n}, i and j being adjacent in O_n if and only if |i − j| is different from 0 and n. It is not difficult to check that O_3 is not a clique graph, K(O_3)=O_4 and, more generally, K(O_n) = O_2^(n−1), n ≥ 3.One longstanding open question had been whether K(J)=K^2(J). In this talk, I will speak about the falseness of this equality, which is deduced from the fact that O_4 ∈ K(G) \ K^2(G). I will also explore the possibility that K^n(O^3) ∈ K^n(G) \ K^(n+1)(G), n ≥ 1, with more emphasis on the case that n=2.