Gráfico dividido

En la teoría de grafos , una rama de las matemáticas, un grafo dividido es un grafo cuyos vértices pueden particionarse en una camarilla y un conjunto independiente . Los grafos divididos fueron estudiados por primera vez por Földes y Hammer ( 1977a , 1977b ) , e introducidos independientemente por Tyshkevich y Chernyak ( 1979 ) , quienes los denominaron "grafos polares" ( en ruso : полярные графы ). ^{[ 1 ]}  

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

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

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

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

Dado que los grafos cordales son perfectos , también lo son los grafos divididos. Los grafos doblemente divididos , una familia de grafos derivados de los grafos divididos mediante la duplicación de cada vértice (de modo que la camarilla induce un antimatching y el conjunto independiente induce un matching), figuran prominentemente como una de las cinco clases básicas de grafos perfectos a partir de las cuales se pueden formar todos los demás en la demostración de Chudnovsky et al. (2006) del Teorema Fuerte de Grafos Perfectos .

Si un grafo es a la vez un grafo dividido y un grafo de intervalo , entonces su complemento es a la vez un grafo dividido y un grafo de comparabilidad , y viceversa. Los grafos de comparabilidad divididos, y por lo tanto también los grafos de intervalo divididos, pueden caracterizarse en términos de un conjunto de tres subgrafos inducidos prohibidos. ^{[ 7 ]} Los cografos divididos son exactamente los grafos umbral . Los grafos de permutación divididos son exactamente los grafos de intervalo que tienen complementos de grafos de intervalo; ^{[ 8 ]} estos son los grafos de permutación de permutaciones fusionadas asimétricas . ^{[ 9 ]} Los grafos divididos tienen número cocromático 2.

Sea G un grafo dividido, particionado en una camarilla C y un conjunto independiente i . Entonces, toda camarilla maximal en un grafo dividido es o bien C mismo, o bien la vecindad de un vértice en i . Por lo tanto, es fácil identificar la camarilla máxima y, complementariamente, el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera: ^{[ 10 ]}

1. Existe un vértice x en i tal que C ∪ { x } es completo. En este caso, C ∪ { x } es una camarilla 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 una camarilla máxima.
3. C es una camarilla máxima e i es un conjunto independiente máximo. En este caso, G tiene una partición única ( C , i ) en una camarilla y un conjunto independiente, C es la camarilla máxima 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, incluyendo 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 . ^{[ 11 ]} También es bien sabido que el problema del conjunto dominante mínimo sigue siendo NP-completo para grafos divididos. ^{[ 12 ]}

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 grafo G d ₁ ≥ d ₂ ≥ … ≥ d _n , y sea m el mayor valor de i tal que d _i ≥ 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 una camarilla máxima en G , y los vértices restantes constituyen un conjunto independiente. ^{[ 13 ]}

La división de un grafo arbitrario mide el grado en que esta desigualdad no se cumple. Si un grafo no es un grafo dividido, la secuencia más pequeña de inserciones y eliminaciones de aristas que lo convierten en un grafo dividido se puede obtener agregando todas las aristas faltantes entre los m vértices con los grados más grandes y eliminando todas las aristas entre pares de los vértices restantes; la división cuenta el número de operaciones en esta secuencia. ^{[ 14 ]}

Royle (2000) demostró que los grafos divididos de n vértices ( sin etiquetar ) están en correspondencia biunívoca con ciertas familias de Sperner . Utilizando este hecho, determinó una fórmula para el número de grafos divididos no isomorfos en n vértices. Para valores pequeños de n , comenzando desde n = 1, estos números son:

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (secuencia A048194 en el OEIS ) .

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

• En el libro de Martin Charles Golumbic , "Teoría algorítmica de grafos y grafos perfectos", aparece un capítulo sobre grafos divididos.