Gráfico trivialmente perfecto

Un gráfico trivialmente perfecto  es un gráfico con la propiedad de que en cada uno de sus subgráficos generados , el tamaño del conjunto independiente máximo (en tamaño) es igual al número de camarillas máximas [1] [2] . Los gráficos trivialmente perfectos fueron estudiados por primera vez por Volk [3] [4] , pero el nombre fue dado por Golumbik [2] . Golumbik escribió que "este nombre fue elegido en vista de la trivialidad de probar que tales gráficos son perfectos ". Los gráficos trivialmente perfectos también se conocen como gráficos de comparabilidad de árbol [3] [4] , gráficos de comparabilidad de árbol [5] y gráficos cuasiumbral.[6] .

Descripciones equivalentes

Los gráficos trivialmente perfectos tienen varias otras descripciones equivalentes:

• Son gráficos de comparabilidad de árboles de la teoría del orden . Es decir, sea T  un orden parcial tal que para cualquier t ∈ T el conjunto { s ∈ T  : s < t } está bien ordenado con relación < y T tiene el menor elemento r . Entonces el gráfico de comparabilidad de orden T es trivialmente perfecto y cualquier gráfico trivialmente perfecto puede formarse de esta manera [7] [8] .
• Son grafos que no contienen un camino P 4 ni un ciclo C 4 como subgrafos generados [7] [9] [10]
• Son grafos en los que cada subgrafo generado conexo contiene un vértice universal [11] .
• Son gráficos que se pueden considerar como gráficos de intervalo de un conjunto de tramos anidados . Un conjunto de huecos tiene la propiedad de anidamiento si para cualesquiera dos huecos del conjunto no se intersecan, o uno de ellos está contenido en el otro [12] .
• Son grafos que son a la vez grafos cordales y cografos [13] [14] . Esto se sigue de la descripción de grafos cordales como grafos sin ciclos generados de longitud cuatro o más y cografos como grafos sin caminos generados con cuatro vértices ( P 4 ).
• Son grafos que son a la vez cografos y grafos de intervalos [13] [14] .
• Son grafos que se pueden formar a partir de grafos con un vértice, usando dos operaciones: una unión separada de dos grafos trivialmente perfectos más pequeños y agregando un nuevo vértice adyacente a todos los vértices del grafo trivialmente perfecto más pequeño [6] [15] . Estas operaciones corresponden a la formación de un nuevo bosque por la unión inconexa de dos bosques más pequeños, ya la formación de un árbol por la unión de una nueva raíz a las raíces de todos los árboles del bosque.
• Son grafos en los que, para cualquier arista uv , las vecindades de los vértices u y v (incluidos u y v ) están anidadas—una vecindad debe ser vecindad de la otra [14] .
• Son gráficos de permutación definidos a partir de permutaciones ordenadas en la pila [16] .
• Son grafos con la propiedad de que en cada uno de sus subgrafos generados , el número de cobertura de camarillas es igual al número de camarillas máximas [17] .
• Son grafos con la propiedad de que en cada uno de sus subgrafos generados , el número clique es igual al pseudonúmero de Grandi [17] .
• Son grafos con la propiedad de que el número cromático de cada uno de sus subgrafos generados es igual al pseudo número de Grandi [17] .

Clases de grafos relacionados

De las descripciones equivalentes de gráficos trivialmente perfectos se sigue que cualquier gráfico trivialmente perfecto es también un gráfico cográfico , cordal , ptolemaico , de intervalos y perfecto .

Los gráficos de umbral  son exactamente aquellos gráficos que son trivialmente perfectos y son el complemento de los gráficos trivialmente perfectos (cografos trivialmente perfectos) [18] [19] .

Los molinos son trivialmente perfectos.

Reconocimiento

Chu [20] describe un algoritmo de tiempo lineal simple para reconocer grafos trivialmente perfectos basado en la búsqueda lexicográfica en amplitud . Cuando el algoritmo LexBFS elimina v del primer conjunto de la cola, el algoritmo verifica que todos los vecinos restantes de v estén en el mismo conjunto. Si no, uno de los subgráficos generados prohibidos se puede construir a partir de v . Si la verificación tiene éxito para todo v , entonces el gráfico es trivialmente perfecto. El algoritmo se puede modificar para probar en tiempo lineal si un gráfico es el complemento de un gráfico trivialmente perfecto.

Determinar si un gráfico general después de eliminar k bordes se convierte en un gráfico trivialmente perfecto es un problema NP-completo [21] , solucionable con parámetros fijos [22] , y se puede resolver en el tiempo O(2.45 k (m+n) ) [ 23] .

Notas

1. ↑ Brandstädt, Le, Spinrad, 1999 , pág. 34 definición 2.6.2.
2. ↑ 1 2 Golumbic, 1978 .
3. ↑ 12 Wolk , 1962 .
4. ↑ 12 Wolk , 1965 .
5. ↑ Donnelly, Isaac, 1999 .
6. ↑ 12 Yan , Chen, Chang, 1996 .
7. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 99 Teorema 6.6.1.
8. ↑ Golumbic, 1978 , pág. corolario 4.
9. ↑ Golumbic, 1978 , pág. teorema 2.
10. ↑ Wolk 1962 demostró esto para gráficos de comparabilidad de bosques enraizados .
11. ↑ Wolk (1962) .
12. ↑ Brandstädt, Le, Spinrad, 1999 , pág. 51.
13. ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 248.
14. ↑ 1 2 3 Yan, Chen, Chang, 1996 , pág. teorema 3.
15. ↑ Gurski, 2006 .
16. ↑ Rotem, 1981 .
17. ↑ 1 2 3 Rubio-Montiel (2015) .
18. ↑ Brandstädt, Le, Spinrad, 1999 , pág. 100 Teorema 6.6.3.
19. ↑ Golumbic, 1978 , pág. corolario 5.
20. ↑ Chu, 2008 .
21. ↑ Sharán (2002) .
22. ↑ Caí (1996) .
23. ↑ Nastos, Gao, 2010 .

Literatura

• Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Clases de grafos: una encuesta. - Monografías SIAM sobre Matemática Discreta y Aplicaciones, 1999. - ISBN 0-89871-432-X .
• Cai L. Trazabilidad de parámetros fijos de problemas de modificación de gráficos para propiedades hereditarias // Cartas de procesamiento de información . - 1996. - T. 58 , núm. 4 . — S. 171–176 . - doi : 10.1016/0020-0190(96)00050-6 .
• Frank Pok Man Chu. Un algoritmo simple basado en LBFS que certifica el tiempo lineal para reconocer gráficos trivialmente perfectos y sus complementos // Letras de procesamiento de información . - 2008. - T. 107 , núm. 1 . — págs. 7–12 . -doi : 10.1016/ j.ipl.2007.12.009 .
• Sam Donnelly, Garth Isaac. Potencias hamiltonianas en grafos de comparabilidad umbral y arborescente // Matemáticas discretas . - 1999. - T. 202 , núm. 1-3 . — págs. 33–44 . - doi : 10.1016/S0012-365X(98)00346-X .
• Martín Charles Golumbic. Gráficos trivialmente perfectos // Matemáticas discretas . - 1978. - T. 24 , núm. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
• Frank Gursky. Caracterizaciones para co-grafos definidos por operaciones restringidas de ancho NLC o ancho de camarilla // Matemáticas discretas . - 2006. - T. 306 , núm. 2 . — S. 271–277 . -doi : 10.1016/ j.disco.2005.11.014 .
• James Nastos, Yong Gao. Una estrategia de ramificación novedosa para problemas de modificación de gráficos parametrizados // Apuntes de clase en informática. - 2010. - T. 6509 . — S. 332–346 .
• Rotem D. Pila de permutaciones clasificables // Matemáticas discretas . - 1981. - T. 33 , núm. 2 . — S. 185–196 . - doi : 10.1016/0012-365X(81)90165-5 .
• Rubio-Montiel C. Una nueva caracterización de grafos trivialmente perfectos // Electronic Journal of Graph Theory and Applications. - 2015. - Vol. 3 , núm. 1 . — P. 22–26 . -doi : 10.5614 / ejgta.2015.3.1.3 .
• Roded Sharan. Problemas de modificación de grafos y sus aplicaciones a la investigación genómica // Tesis doctoral, Universidad de Tel Aviv. — 2002.
• Wolk ES El gráfico de comparabilidad de un árbol // Actas de la American Mathematical Society . - 1962. - T. 13 , núm. 5 . — S. 789–795 . -doi : 10.1090 / S0002-9939-1962-0172273-0 .
• Wolk ES Una nota sobre el gráfico de comparabilidad de un árbol // Actas de la American Mathematical Society . - 1965. - T. 16 . — P. 17–20 . -doi : 10.1090 / S0002-9939-1965-0172274-5 .
• Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Gráficos cuasi-umbral // Matemática Aplicada Discreta . - 1996. - T. 69 , núm. 3 . — S. 247–255 . - doi : 10.1016/0166-218X(96)00094-7 .

Enlaces

• Gráficos trivialmente perfectos , Sistema de información sobre clases de gráficos y sus inclusiones , < http://www.graphclasses.org/classes/gc_327.html >