ARS 101: Grafo dividido

Grafo dividido
Wikipedia


Un grafo dividido, dividido en una agrupación y un conjunto independiente.

En la 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 agrupación 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). [1]

Un grafo dividido puede tener más de una partición en una agrupación y un conjunto independiente; Por ejemplo, la trayectoria a-b-c es un grafo dividido, cuyos vértices se pueden dividir en tres formas 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 se divide si y sólo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de enlaces disjuntos (el complemento de un ciclo de 4). 2]

Relación con otras familias de grafos

De la definición, los grafos divididos se clausuran claramente bajo complementación. [3] Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos son también acordales. [4] Del mismo modo que los grafos acordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de los distintos subestados de los grafos en estrella. Casi todos los grafos acordales son grafos divididos; Es decir, en el límite cuando n va al infinito, la fracción de los grafos acordales de n-vértices que se dividen se aproxima a uno. [6]

Debido a que los grafos acordales son perfectos, también lo son los grafos divididos. Los grafos de doble división, una familia de grafos derivados de grafos divididos, duplicando cada vértice (por lo que la camarilla viene a inducir un antimatching y el conjunto independiente viene a inducir una correspondencia), figura prominentemente 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 Strong Perfect Graph.

Si un grafo es a la vez un grafo dividido y un grafo de intervalo, 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 de intervalo divididos, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos. [7] Los cógrafos divididos son exactamente los gráficos de umbral, y los grafos de permutación dividida son exactamente los grafos de intervalos que tienen complementos de grafos de intervalos. [8] Los grafos divididos tienen el número 2 cocromático.

Problemas Algorítmicos

Sea G un grafo dividido, dividida en un clique C y un conjunto independiente I. Entonces cada camarilla máxima en un grafo dividido es C o la vecindad de un vértice en I. Por lo tanto, es fácil identificar la máxima camarilla , 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 una máxima 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 máximo independiente y C es un máximo clique.
3. C es una camarilla máxima e I es un conjunto independiente máximo. En este caso, G tiene una única partición (C, I) en una camarilla y un conjunto independiente, C es la máxima camarilla, e I es el conjunto máximo independiente.

Algunos otros problemas de optimización que son NP-completos en las familias de grafos más generales, incluyendo el grafos coloreados, son similares en los grafos de división. Encontrar un ciclo hamiltoniano sigue siendo NP-completo, incluso para los grafos divididos que son los grafos de cuerdas fuertes. [10] También es bien sabido que el problema del Conjunto Dominador Mínimo sigue siendo NP-completo para los grafos divididos. [11]

Secuencias de grados

Una característica notable de los grafos divididos es que pueden ser reconocidos únicamente a partir de sus secuencias de grados. Sea la sucesión 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



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.

Cuenta de grafos divididos

Royle (2000) demostró que las grafos divididos de n-vértices con n están en correspondencia uno a uno con ciertas familias de Sperner. Usando este hecho, determinó una fórmula para el número de grafos (no isomórficos) divididos 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, ... (secuencia A048194 en el OEIS).

Este resultado de enumeración gráfica también fue demostrado antes por Tyshkevich y Chernyak (1990).

Notas

1. Földes & Hammer (1977a) tenían una definición más general, en la que los grafos que llamaron grafos divididos también incluían grafos bipartitos (es decir, grafos que se dividen en dos conjuntos independientes) y los complementos de los grafos bipartitos (es decir, los grafos que se pueden dividir en dos grupos) . Földes & Hammer (1977b) utilizan la definición aquí dada, que se ha seguido en la literatura subsiguiente; Por ejemplo, es Brandstädt, Le & Spinrad (1999), Definition 3.2.3, p.41.
2. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.
3. Golumbic (1980), Theorem 6.1, p. 150.
4. Földes & Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt, Le & Spinrad (1999), Theorem 3.2.3, p. 41.
5. McMorris & Shier (1983); Voss (1985); Brandstädt, Le & Spinrad (1999), Theorem 4.4.2, p. 52.
6. Bender, Richmond & Wormald (1985).
7. Földes & Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.
8. Brandstädt, Le & Spinrad (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
9. Hammer & Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.
10. Müller (1996)
11. Bertossi (1984)
12. Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow & Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt, Le & Spinrad (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.

Referencias

• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi:10.1017/S1446788700023077, MR 0770128.
• Bertossi, Alan A. (1984), "Dominating sets for split and bipartite graphs", Information Processing Letters, 19: 37–40, doi:10.1016/0020-0190(84)90126-1.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, doi:10.4007/annals.2006.164.51, MR 2233847.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860.
• Földes, Stéphane; Hammer, Peter Ladislaw (1977b), "Split graphs having Dilworth number two", Canadian Journal of Mathematics, 29 (3): 666–672, doi:10.4153/CJM-1977-069-1, MR 0463041.
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7, MR 0562306.
• Hammer, Peter Ladislaw; Simeone, Bruno (1981), "The splittance of a graph", Combinatorica, 1 (3): 275–284, doi:10.1007/BF02579333, MR 0637832.
• McMorris, F. R.; Shier, D. R. (1983), "Representing chordal graphs on K1,n", Commentationes Mathematicae Universitatis Carolinae, 24: 489–494, MR 0730144.
• Merris, Russell (2003), "Split graphs", European Journal of Combinatorics, 24 (4): 413–430, doi:10.1016/S0195-6698(03)00030-1, MR 1975945.
• Müller, Haiko (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
• Royle, Gordon F. (2000), "Counting set covers and split graphs" (PDF), Journal of Integer Sequences, 3 (2): 00.2.6, MR 1778996.
• Tyshkevich, Regina I. (1980), "[The canonical decomposition of a graph]", Doklady Akademii Nauk SSSR (in Russian), 24: 677–679, MR 0587712
• Tyshkevich, Regina I.; Chernyak, A. A. (1979), "Canonical partition of a graph defined by the degrees of its vertices", Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk (en ruso), 5: 14–26, MR 0554162.
• Tyshkevich, Regina I.; Chernyak, A. A. (1990), Еще один метод перечисления непомеченных комбинаторных объектов, Matem. Zametki (in Russian), 48 (6): 98–105, MR 1102626. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), Mathematical notes of the Academy of Sciences of the USSR 48 (6): 1239–1245, doi:10.1007/BF01240267.
• Tyshkevich, Regina I.; Melnikow, O. I.; Kotov, V. M. (1981), "On graphs and degree sequences: the canonical decomposition", Kibernetika (in Russian), 6: 5–8, MR 0689420.
• Voss, H.-J. (1985), "Note on a paper of McMorris and Shier", Commentationes Mathematicae Universitatis Carolinae, 26: 319–322, MR 0803929.