Grafo dividido

A partir de la definición, los grafos divididos están claramente cerrados bajo complementación .[3] Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos también son cordales.[4] Así como los grafos cordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de distintas subestrellas de los grafos de estrellas .[5] Casi todos los grafos cordales son grafos divididos; es decir, en el límite cuando n tiende a infinito, la fracción de gráficos cordales de n vértices que se dividen se aproxima a uno.[6]

Debido a que los grafos cordales son perfectos, también lo son los grafos divididos. Los grafos de división doble, una familia de grafos derivados de grafos divididos al duplicar cada vértice (de modo que la camarilla llega a inducir un antiemparejamiento y el conjunto independiente viene a inducir un emparejamiento), figura de manera destacada como una de las cinco clases básicas de grafos perfectos de los cuales todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del teorema del gráfico perfecto fuerte .

Si un grafos es a la vez un grafos dividido y un grafos de intervalos, entonces su complemento es tanto un gráfico dividido como un grafo de comparabilidad, y viceversa. Los grafos de comparabilidad dividida y, por lo tanto, también los grafos de intervalo dividido, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos.[7] Los cografos divididos son exactamente los grafos de umbral . Los grafos de permutación dividida son exactamente los grafos de intervalo que tienen complementos de grafo de intervalo;[8] estos son los grafos de permutación de permutaciones combinadas sesgadas . [9] Los grafos divididos tienen el número cocromático 2.

Sea G un grafo dividido, dividido en una camarilla C y un conjunto independiente i . Entonces, cada clique máximo en un grafo dividido es C en sí mismo o la vecindad de un vértice en i . Por lo tanto, es fácil identificar el clique máximo y, complementariamente, el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera:[9]

1. Existe un vértice x en i tal que C ∪ {x} es completo. En este caso, C ∪ {x} es un clique máxima e i es un conjunto independiente máximo.
2. Existe un vértice x en C tal que i ∪ {x} es independiente. En este caso, i ∪ {x} es un conjunto independiente máximo y C es un clique máxima.
3. C es un clique máximo e i es un conjunto independiente máximo. En este caso, G tiene una partición única (C, i) en un clique y un conjunto independiente, C es el clique máximo e i es el conjunto independiente máximo.

Algunos otros problemas de optimización que son NP-completos en familias de grafos más generales, incluida la coloración de grafos, son igualmente sencillos en grafos divididos. Encontrar un ciclo hamiltoniano sigue siendo NP-completo incluso para grafos divididos que son grafos fuertemente cordales .[10] También es bien sabido que el problema del Conjunto Dominante Mínimo sigue siendo NP-completo para grafos divididos.[11]

Una propiedad notable de los grafos divididos es que pueden reconocerse únicamente a partir de sus secuencias de grados . Sea la secuencia de grados de un gráfico G ${\displaystyle d_{1}\geq d_{2}\geq \ldots \geq d_{n}}$, y sea m el mayor valor de i tal que ${\displaystyle d_{i}\geq i-1}$ . Entonces G es un grafo dividido si y solo si

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

Si este es el caso, entonces los m vértices con los grados más grandes forman un clique máxima en G, y los vértices restantes constituyen un conjunto independiente.[12]

La división de un grafo arbitrario mide hasta qué punto esta desigualdad no se cumple. Si un grafo no es un grafo dividido, entonces se puede obtener la secuencia más pequeña de inserciones y eliminaciones de bordes que lo convierten en un gráfico dividido sumando todos los bordes que faltan entre los m vértices con los grados más grandes y eliminando todos los bordes entre pares de los vértices restantes; la división cuenta el número de operaciones en esta secuencia. [14]

Royle (2000) mostró que los grafos divididos en n vértices con n tienen una correspondencia biunívoca con ciertas familias de Sperner. Utilizando este hecho, determinó una fórmula para el número de gráficos divididos no isomorfos en n vértices. Para valores pequeños de n, a partir de n = 1, estos números son

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696,... (sucesión A048194 en OEIS) .

Este resultado enumerativo también fue probado anteriormente por Tyshkevich y Chernyak (1990) .

• Un capítulo sobre gafos divididos aparece en el libro de Martin Charles Golumbic, "Teoría de grafos algorítmicos y grafos perfectos".