En la teoría de grafos , un gráfico clique de un grafo no dirigido G es otro gráfico K ( G ) que representa la estructura de camarillas en G .
Los gráficos de camarillas se discutieron al menos ya en 1968, [1] y en 1971 se dio una caracterización de los gráficos de camarillas [2].
A clique de un gráfico 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 máxima de un gráfico G es una camarilla X de vértices de G , de modo que no hay una camarilla Y de vértices de G que contenga todo X y al menos otro vértice.
El gráfico clique K ( G ) también se puede caracterizar como el gráfico de intersección de la máxima camarillas de G . [3]
Un gráfico H es el gráfico de camarillas K ( G ) de otro gráfico si y solo si existe una colección C de camarillas en H cuya unión cubre todos los bordes 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 también debería tener una intersección no vacía. Sin embargo, las camarillas en C no necesariamente tienen que ser camarillas máximas. [2]
Cuando H = K ( G ), se puede construir una familia C de este tipo en la que cada camarilla en C corresponde a un vértice v en G , y consiste en las camarillas en G que contienen v . Estas camarillas todos tienen v en su intersección, de modo que formen una camarilla en H . La familia C construida de esta manera tiene la propiedad Helly, porque cualquier subfamilia de C con intersecciones no vacías por pares debe corresponder a una camarilla en G, que puede extenderse a una camarilla máxima que pertenece a la intersección de la subfamilia. [2]