Complemento gráfico

El complemento de un gráfico ( gráfico inverso ) es un gráfico que tiene el mismo conjunto de vértices que el gráfico dado , pero en el que dos vértices no coincidentes son adyacentes si y solo si no son adyacentes en .

Formalmente, para un grafo simple y  - el conjunto de todos los subconjuntos de dos elementos de sus vértices - el complemento se define como un par  - un grafo con el conjunto original de vértices y con un conjunto de aristas obtenidas del grafo completo eliminando esos en el gráfico dado.

El complemento de un grafo vacío (que contiene solo vértices y ningún borde) es un grafo completo y viceversa. Un conjunto independiente de un grafo es una camarilla en el complemento del grafo, y viceversa. El complemento de cualquier gráfico sin triángulos no contiene garras .

Un grafo autocomplementario  es un grafo que es isomorfo a su complemento. Los cografos se definen como gráficos que se pueden construir a partir de un solo punto mediante una operación de unión y complemento no relacionada. Los cografos forman una familia de grafos autocomplementarios: el complemento de cualquier cografo es otro cografo (posiblemente diferente del original).

Literatura