Finding clique pseudo-inverses of graphs

MIGUEL ÁNGEL PIZAÑA; PABLO DE CARIA

Congreso; International Workshop on Combinatorial and Computational Aspects of Optimization, Topology and Algebra (ACCOTA 2014); 2014

Dado un grafo G, el grafo clique de G tiene como vértices a los cliques de G, siendo dos de ellos adyacentes si y sólo si tienen intersección no vacía. Se denota por K al operador que asigna a todo grafo su grafo clique. Dado un número natural n, K^n es la composición de K consigo mismo n veces. Sea J la clase de todos los grafos. Determinar si la desigualdad K(J)=K^2(J) es falsa fue un problema abierto por varios años, que ha sido resuelto recientemente demostrando que el grafo clique del octaedro está en K(J) pero no en K^2(J). Llamemos O_3 al octaedro. Luego de haberse resuelto el problema, se sospechó que K(O_3) está en K^2(J) pero no en K^3(J). Sin embargo, eso no resultó ser así: K^2(O3) es igual a K^3(L(O_3)), donde el significado de L es grafo de líneas. Dicho de otro modo, K^2 es invariante cuando se le aplica el operador K ◦ L a O_3. En esta charla, encontraremos una clase de grafos que satisface esta misma invarianza. Al ser esta clase de grafos bastante limitada, nos iniciaremos en la búsqueda, para grafos fuera de ella, de operadores con imagen en K(J) que preserven K^2. Al hacer esto, hay dos objetivos antagónicos que se tienen en vista: demostrar que K^2(J) =K^3(J) o, en caso de que esto sea falso, refinar la búsqueda de un grafo en K^2(J) pero no en K^3(J) a través del descarte de la mayor cantidad posible de candidatos.