Definición de cubierta de camarilla y cubierta de arista de camarilla

Question

En Wikipedia

El problema de la cobertura de camarillas (también llamado partición en cliques) es el problema de determinar si los vértices de un grafo pueden ser particionado en k camarillas.

Me parece que una cubierta de camarilla se define como un conjunto de camarillas que partición los vértices del grafo.

En Wikipedia :

Una definición alternativa del número de intersección de un grafo G es es el menor número de camarillas de G (subgrafos completos de G) que juntos portada todas las aristas de G. Un conjunto de cliques con esta propiedad se conoce como cubierta de aristas en clique o cubierta de aristas en clique borde,

Me parece que una cubierta de borde de camarilla se define como un conjunto de camarillas que portada los vértices del grafo.

Los dos no me parecen coherentes. He buscado en Introducción a la teoría de grafos de Douglas West, Tanto la cobertura de camarilla como la cobertura de arista de camarilla se definen en términos de cobertura en lugar de partición. Así que me pregunto si la definición de cobertura de camarilla en Wikipedia es incorrecta.

Gracias.

Answer 1

A cobertura de vértices es un conjunto de camarillas que cubren todas las vértices de un gráfico. Si se solapan, es decir, dos camarillas comparten el vértice $v$ podríamos simplemente eliminar $v$ de una de las dos camarillas y acabaríamos con una cubierta de camarilla de vértices del mismo tamaño o menor (menor si la camarilla fuera sólo $v$ ). Así que, en este caso, seguimos adelante y definimos las camarillas como disjuntas. En número de cobertura de vértices es el menor número de tales camarillas necesarias para cubrir todos los vértices. Este número sería el mismo tanto si especificáramos cliques disjuntas como si no, porque si una cobertura mínima de cliques de vértices contuviera cliques que se solaparan, podríamos eliminar vértices de una u otra hasta que dejaran de solaparse. Por tanto, es equivalente a dividir los vértices en camarillas.

En cubierta de la camarilla de borde es un conjunto de camarillas que cubren todas las bordes . No podemos garantizar que sean disjuntos, por lo que hablar de partición no tiene sentido en este caso. Tomemos una estrella, por ejemplo, $K_{1, 3}$ . Para cubrir las 3 aristas, necesitaremos que cada arista sea una camarilla y que las 3 camarillas contengan el vértice central de la estrella. De nuevo, podemos definir la número de cubierta de la camarilla de borde como el menor número de tales camarillas necesarias para cubrir todas las aristas.

Por lo tanto, ambas podrían considerarse en términos de coberturas, pero sólo la cobertura de la camarilla de vértices podría considerarse en términos de particiones.

De estas definiciones se deduce claramente que el número de cubiertas de vértices es menor o igual que el número de cubiertas de aristas. Además, el número de cobertura de clicas de vértices de un grafo es simplemente igual al número cromático del complemento de ese grafo. Véase aquí para la idea básica de una prueba.