stringtranslate.com

Gráfico dividido

Un gráfico dividido, particionado en una camarilla y un conjunto independiente.

En teoría de grafos , una rama de las matemáticas, un grafo dividido es un grafo en el que los vértices se pueden dividir en una camarilla y un conjunto independiente . Los grafos divididos fueron estudiados por primera vez por Földes y Hammer  (1977a, 1977b), y fueron introducidos de forma independiente por Tyshkevich y Chernyak (1979), donde llamaron a estos grafos "grafos polares" ( en ruso : полярные графы ). [1]

Un gráfico dividido puede tener más de una partición en una camarilla y un conjunto independiente; por ejemplo, la ruta a – b – c es un gráfico dividido, cuyos vértices se pueden dividir 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 gráficos divididos se pueden caracterizar en términos de sus subgráficos inducidos prohibidos : un gráfico está dividido si y solo si ningún subgráfico 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 gráficos

De la definición, los grafos partidos están claramente cerrados bajo complementación . [3] Otra caracterización de los grafos partidos involucra 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 partidos son los grafos de intersección de subestrellas distintas de grafos estrella . [5] Casi todos los grafos cordales son grafos partidos; es decir, en el límite cuando n tiende a infinito, la fracción de grafos cordales de n -vértices que están partidos se acerca a uno. [6]

Como los grafos cordales son perfectos , también lo son los grafos divididos. Los grafos doblemente divididos , 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 llega a inducir un emparejamiento), 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 prueba de Chudnovsky et al. (2006) del Teorema del grafo perfecto fuerte .

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, 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 divididos son exactamente los grafos de intervalo que tienen complementos de grafo de intervalo; [8] estos son los grafos de permutación de permutaciones fusionadas sesgadas . [9] Los grafos divididos tienen 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 camarilla máxima en un grafo dividido es C en sí misma, o 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 un grupo máximo e i es un conjunto máximo independiente.
  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, 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 . [11] También es bien sabido que el problema del conjunto mínimo dominante sigue siendo NP-completo para grafos divididos. [12]

Secuencias de grados

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 1 ≥ d 2 ≥ … ≥ d n , y sea m el valor más grande de i tal que d i ≥ i – 1 . Entonces G es un grafo dividido si y solo si

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 el que esta desigualdad no es verdadera. Si un grafo no es un grafo dividido, entonces la secuencia más pequeña de inserciones y eliminaciones de aristas que lo convierten en un grafo dividido se puede obtener sumando todas las aristas faltantes entre los m vértices con los grados más altos 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]

Contando gráficos divididos

Royle (2000) demostró que los grafos divididos de n vértices ( no etiquetados ) están en correspondencia uno a uno 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 la OEIS ).

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

Notas

  1. ^ Földes y Hammer (1977a) tenían una definición más general, en la que los grafos que ellos llamaban grafos divididos también incluían grafos bipartitos (es decir, grafos que se pueden dividir en dos conjuntos independientes) y los complementos de grafos bipartitos (es decir, grafos que se pueden dividir en dos grupos). Földes y Hammer (1977b) utilizan la definición dada aquí, que ha sido seguida en la literatura posterior; por ejemplo, es Brandstädt, Le y Spinrad (1999), Definición 3.2.3, p.41.
  2. ^ Földes y martillo (1977a); Golumbic (1980), Teorema 6.3, pág. 151.
  3. ^ Golumbic (1980), Teorema 6.1, pág. 150.
  4. ^ Földes y martillo (1977a); Golumbic (1980), Teorema 6.3, pág. 151; Brandstädt, Le y Spinrad (1999), Teorema 3.2.3, pág. 41.
  5. ^ McMorris y Shier (1983); Voss (1985); Brandstädt, Le y Spinrad (1999), Teorema 4.4.2, pág. 52.
  6. ^ Bender, Richmond y Wormald (1985).
  7. ^ Földes y martillo (1977b); Golumbic (1980), Teorema 9.7, página 212.
  8. ^ Brandstädt, Le y Spinrad (1999), Corolario 7.1.1, p. 106, y Teorema 7.1.2, p. 107.
  9. ^ Kézdy, Snevily y Wang (1996).
  10. ^ Hammer y Simeone (1981); Golumbic (1980), Teorema 6.2, pág. 150.
  11. ^ Müller (1996)
  12. ^ Bertossi (1984)
  13. ^ Hammer y Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow y Kotov (1981); Golumbic (1980), Teorema 6.7 y Corolario 6.8, pág. 154; Brandstädt, Le y Spinrad (1999), Teorema 13.3.2, pág. 203. Merris (2003) investiga más a fondo las secuencias de grados de los grafos divididos.
  14. ^ Martillo y Simeone (1981).

Referencias

Lectura adicional