Grafo dividido

Se sigue claramente de la definición que los grafos divididos están cerrados bajo complementación.^[3] Otra caracterización de los grafos divididos de igual modo implica la complementación: son grafos cordales cuyos complementos también son cordales.^[4] Así como todo grafo cordal es un grafo de intersección de una familia de subárboles de un árbol, todo grafo dividido es un grafo de intersección de una familia de subestrellas de una estrella .^[5] Casi todos los grafos cordales son grafos divididos; es decir, en el límite cuando ${\displaystyle n}$ tiende a infinito, la fracción de gráficos cordales de ${\displaystyle n}$ vértices que son escindibles se aproxima a uno.^[6]

Debido a que los grafos cordales son perfectos, también los grafos divididos lo son. Los grafos escindibles duplicados, una familia de grafos obtenidos a partir de los grafos escindibles al duplicar cada vértice (de modo que el conjunto obtenido del clan induce un antiemparejamiento y el conjunto obtenido del independiente induce 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 fuerte de la gráfica perfecta.

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

Sea ${\displaystyle G}$ un grafo dividido cuyo conjunto de vértices admite una partición en un clan ${\displaystyle C}$ y un conjunto independiente ${\displaystyle S}$. Entonces, cada clan máximo en un grafo dividido es o bien ${\displaystyle C}$ o la vecindad cerrada de un vértice en ${\displaystyle S}$. Por lo tanto, es fácil identificar el clan 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 ${\displaystyle x}$ en ${\displaystyle S}$ tal que ${\displaystyle C\cup \{x\}}$ es completo. En este caso, ${\displaystyle C\cup \{x\}}$ es un clan máximo y ${\displaystyle S}$ es un conjunto independiente máximo.
2. Existe un vértice ${\displaystyle s}$ en ${\displaystyle C}$ tal que ${\displaystyle S\cup \{x\}}$ es independiente. En este caso, ${\displaystyle S\cup \{x\}}$ es un conjunto independiente máximo y ${\displaystyle C}$ es un clan máximo.
3. ${\displaystyle C}$ es un clan máximo y ${\displaystyle S}$ es un conjunto independiente máximo. En este caso, ${\displaystyle G}$ tiene una partición única ${\displaystyle (C,S)}$ en un clan y un conjunto independiente, ${\displaystyle C}$ es el clan máximo y ${\displaystyle S}$ es el conjunto independiente máximo.

Algunos otros problemas de optimización que son NP-difíciles en familias de grafos más generales, incluida la coloración de grafos, también son tratables en grafos divididos. Determinar la existencia de un ciclo hamiltoniano sigue siendo NP-completo incluso para grafos dvididos que son 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 en tiempo lineal sobre el número de vértices únicamente a partir de sus sucesiones de grados. Si ${\displaystyle d_{1}\geq d_{2}\geq \ldots \geq d_{n}}$ es la sucesión de grados de una gráfica ${\displaystyle G}$ y ${\displaystyle m}$ es el mayor valor de ${\displaystyle i}$ tal que ${\displaystyle d_{i}\geq i-1}$, entonces ${\displaystyle G}$ es una gráfica escindible 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 ${\displaystyle m}$ vértices con los grados más grandes forman un clan máximo en ${\displaystyle G}$, y los vértices restantes constituyen un conjunto independiente.^[12]

El número de escisión de una gráfica arbitraria mide qué tan lejos esta desigualdad está de cumplirse. Si una gráfica no es escindible, entonces se puede considerar la sucesión más corta de inserciones y eliminaciones de aristas que la convierten en una gráfica escindible. La longitud de dicha sucesión puede calcularse sumando el número de aristas que faltan entre los ${\displaystyle m}$ vértices con los grados más grandes y el número de aristas que existen entre pares de los vértices restantes.^[13]

Royle (2000) mostró que los grafos divididos de orden ${\displaystyle n}$ tienen una correspondencia biyectiva con ciertas familias de Sperner. Utilizando este hecho, determinó una fórmula para el número de grafos divididos no isomorfos de orden ${\displaystyle n}$. Para valores pequeños de ${\displaystyle n}$, a partir de ${\displaystyle 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) .