Grafo dividido

En la teoría de grafos, una rama de las matemáticas, un grafo dividido (o el grafo split) es un grafo en el que los vértices se pueden dividir en una clique y un conjunto independiente . Los grafos divididos fueron estudiados por primera vez por Földes y Hammer (1977), e introducido independientemente por Tyshkevich y Cherniak (1979).^[1]​

Un grafo dividido puede tener más de una partición en un clique y un conjunto independiente; por ejemplo, el camino a–b–c es un grafo dividido, cuyos vértices se pueden dividir de tres maneras diferentes:

1. el clique {a, b} y el conjunto independiente {c}
2. el clique {b, c} y el conjunto independiente {a}
3. el clique {b} y el conjunto independiente {a, c}

Los grafos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos : un gráfico se divide si y solo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de aristas disjuntas (el complemento de un 4-ciclo).^[2]​

Relación con otras familias de grafos

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.

Problemas algorítmicos

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]​

Secuencias de grado

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]

Contando gráficos divididos

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) .

Referencias

Bibliografía

Otras lecturas

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