En teoría de grafos , un grafo de camarilla de un grafo no dirigido G es otro grafo K ( G ) que representa la estructura de camarillas en G .
Los gráficos de camarillas se discutieron al menos desde 1968, [1] y una caracterización de los gráficos de camarillas se dio en 1971. [2]
Una camarilla de un grafo G es un conjunto X de vértices de G con la propiedad de que cada par de vértices distintos en X son adyacentes en G. Una camarilla maximal de un grafo G es una camarilla X de vértices de G , tal que no existe ninguna camarilla Y de vértices de G que contenga todo X y al menos otro vértice.
Dado un grafo G , su grafo de camarilla K ( G ) es un grafo tal que
Es decir, el gráfico de camarillas K ( G ) es el gráfico de intersección de las camarillas máximas de G . [3]
Un grafo H es el grafo clique K ( G ) de otro grafo si y solo si existe una colección C de cliques en H cuya unión cubre todas las aristas de H , de modo que C forma una familia Helly . Esto significa que, si S es un subconjunto de C con la propiedad de que cada dos miembros de S tienen una intersección no vacía, entonces S mismo también debería tener una intersección no vacía. Sin embargo, los cliques en C no necesariamente tienen que ser cliques maximales. [2]
Cuando H = K ( G ), se puede construir una familia C de este tipo en la que cada clique en C corresponde a un vértice v en G , y consiste en los cliques en G que contienen a v . Todos estos cliques tienen v en su intersección, por lo que forman un clique en H . La familia C construida de esta manera tiene la propiedad de Helly, porque cualquier subfamilia de C con intersecciones no vacías por pares debe corresponder a un clique en G , que puede extenderse a un clique maximal que pertenece a la intersección de la subfamilia. [2]
Por el contrario, cuando H tiene una familia Helly C de sus camarillas, que cubre todas las aristas de H , entonces es el grafo de camarilla K ( G ) para un grafo G cuyos vértices son la unión disjunta de los vértices de H y los elementos de C . Este grafo G tiene una arista para cada par de camarillas en C con intersección no vacía, y para cada par de un vértice de H y una camarilla en C que lo contiene. Sin embargo, no contiene ninguna arista que conecte pares de vértices en H . Las camarillas máximas en este grafo G consisten cada una en un vértice de H junto con todas las camarillas en C que lo contienen, y su grafo de intersección es isomorfo a H . [2]
Sin embargo, esta caracterización no conduce a algoritmos eficientes: el problema de reconocer si un gráfico dado es un gráfico de camarilla es NP-completo . [4]