Gráfico dividido

En la teoría de grafos, un gráfico dividido es un gráfico en el que los vértices se pueden dividir en una camarilla y un conjunto independiente . Los gráficos divididos fueron estudiados por primera vez por Földes y Hammer [1] [2] , y Tyszkiewicz y Czernyak [3] [4] los introdujeron de forma independiente .

Un gráfico dividido puede tener varias descomposiciones por camarilla y un conjunto independiente. Por lo tanto, el camino a - b - c se divide y se puede dividir de tres maneras diferentes:

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

Los gráficos divisibles se pueden caracterizar en términos de sus subgráficos prohibidos : un gráfico se divide si y solo si ningún subgráfico generado es un ciclo con cuatro o cinco vértices, y tampoco hay un par de vértices desconectados (es decir, el complemento de un ciclo). de 4 vértices) [5 ] [6] .

Relación con otras familias de grafos

Por definición, la clase de grafos divididos es cerrada con respecto a la operación complemento [7] . Otra característica de los gráficos divididos que implica complemento son los gráficos cordales , cuyos complementos también son cordales [8] . Dado que los gráficos cordales son gráficos de intersección de subárboles de árboles, los gráficos divididos son gráficos de intersección de diferentes subestrellas de estrellas [9] . Casi todos los gráficos cordales son gráficos divididos. Es decir, como n tiende a infinito, el cociente del número de grafos cordales con n vértices al número de grafos separables tiende a uno [10] .

Dado que los gráficos cordales son perfectos , los gráficos divisibles también lo son. Gráficos de doble división , una familia de gráficos obtenidos a partir de gráficos divididos al duplicar el número de vértices (de modo que una camarilla da una anticoincidencia: un conjunto de bordes separados como máximo 2, y un conjunto independiente se convierte en una coincidencia), aparece como uno de las cinco clases principales de gráficos perfectos a partir de los cuales se pueden construir todos los demás para probar el teorema riguroso del gráfico perfecto [11] .

Si un gráfico es a la vez divisible y de intervalo , entonces su complemento es a la vez divisible y un gráfico de comparabilidad , y viceversa. Los gráficos de comparabilidad divisibles y, por lo tanto, los gráficos de intervalos divisibles, se pueden describir en términos de tres subgráficos prohibidos [12] . Las cografías divididas son  exactamente gráficas de umbral , y las gráficas de permutación divididas  son exactamente gráficas de intervalo cuyos complementos también son de intervalo [13] . El número cocromático de los gráficos divididos es 2.

Máxima camarilla y máximo conjunto independiente

Sea G  un grafo dividido descompuesto en una camarilla C y un conjunto independiente I . Entonces, cualquier camarilla máxima en el gráfico dividido coincide con C o es una vecindad de un vértice de I. Así, en un grafo dividido, es fácil encontrar la camarilla máxima y, además, el conjunto independiente máximo . Cualquier gráfico divisible debe tener una de las siguientes declaraciones [14] :

  1. Hay un vértice x en I tal que C ∪ { x } es completo. En este caso, C ∪ { x } es una camarilla maximal e I  es un conjunto independiente maximal.
  2. Hay un vértice x en C tal que I ∪ { x } es un conjunto independiente. En este caso, I ∪ { x } es un conjunto independiente maximal y C  es una camarilla maximal.
  3. C es la camarilla más grande y I el conjunto independiente más grande. En este caso, G tiene una descomposición única ( C , I ) en una camarilla y un conjunto independiente, C es una camarilla maximal e I es un conjunto independiente maximal.

Algunos otros problemas de optimización que son NP-completos en familias de gráficos más generales, incluida la coloración , se resuelven simplemente en gráficos divididos.

Secuencias de grado

Una de las grandes propiedades de los gráficos divididos es que se pueden reconocer únicamente por sus secuencias de grados de vértices . Sea d 1 ≥ d 2 ≥ … ≥ d n  la secuencia de grados de vértice del gráfico G y m  el mayor valor de i para el cual d i ≥ i  - 1. Entonces G es un gráfico dividido si y solo si

Si esto es cierto, entonces los m vértices con los grados más grandes forman una camarilla máxima G y los vértices restantes forman un conjunto independiente [15] .

Contando gráficos divididos

Royle [16] mostró que los gráficos divididos con n vértices corresponden uno a uno a ciertas familias de Sperner . Usando este hecho, encontró una fórmula para el número de gráficos divididos (no isomorfos) con 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,... Secuencia OEIS A048194 .

Esta enumeración fue probada previamente por Tyszkiewicz y Chernyak [17] .

Notas

  1. ↑ Földes, Hammer, 1977a .
  2. ↑ Földes, Hammer, 1977b .
  3. ↑ Tyshkevich, Cherniak, 1979 .
  4. ↑ Földes y Hammer Földes, Hammer, 1977a dio una definición más general en la que los gráficos que llaman divisibles también incluyen gráficos bipartitos (es decir, gráficos divididos en dos conjuntos independientes) y complementos de gráficos bipartitos (es decir, gráficos que se pueden descomponer en dos camarillas). Földer y Hammer Földes, Hammer, 1977b dan la definición dada aquí y utilizada en la literatura posterior, por ejemplo, Brandstädt, Le y Spinrad Brandstädt, Le, Spinrad, 1999 , Definición 3.2.3, p. 41
  5. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Teorema 6.3, página 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Algoritmos de reconocimiento de certificación de tiempo lineal y subgrafos inducidos prohibidos // Nordic Journal of Computing. - 2007. - T. 14 .
  7. ↑ Golumbic, 1980 , Teorema 6.1, página 150.
  8. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Teorema 6.3, página 151; Brandstädt, Le, Spinrad, 1999 , Teorema 3.2.3, p. 41.
  9. ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , Teorema 4.4.2, página 52.
  10. ↑ Bender, Richmond, Wormald, 1985 .
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  12. ↑ Földes, Hammer, 1977b ; Golumbic, 1980 , Teorema 9.7, página 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999 , Corolario 7.1.1, página 106 y Teorema 7.1.2, página 107.
  14. ↑ Martillo, Simeone, 1981 ; Golumbic, 1980 , Teorema 6.2, página 150.
  15. ↑ Martillo, Simeone, 1981 ; Tyshkévich, 1980 ; Tyshkevich, Melnikov, Kotov, 1981 ; Golumbic, 1980 , Teorema 6.7 y Corolario 6.8, página 154; Brandstädt, Le, Spinrad, 1999 , Teorema 13.3.2, página 203. Merris, 2003 consideración adicional de la secuencia de grados de gráficos divididos.
  16. ↑ Royle, 2000 .
  17. ↑ Tyshkevich, Cherniak, 1990 .

Literatura

Lecturas adicionales