Gráfico trivialmente perfecto

En teoría de grafos , un gráfico trivialmente perfecto es un gráfico con la propiedad de que en cada uno de sus subgrafos inducidos el tamaño del conjunto independiente máximo es igual al número de camarillas máximas . ^[1] Los gráficos trivialmente perfectos fueron estudiados por primera vez por (Wolk 1962, 1965), pero fueron nombrados por Golumbic (1978); Golumbic escribe que "se eligió el nombre porque es trivial demostrar que tal gráfico es perfecto ". Los gráficos trivialmente perfectos también se conocen como gráficos de comparabilidad de árboles , ^[2] gráficos de comparabilidad arborescentes , ^[3] y gráficos de cuasi-umbral . ^[4]

Caracterizaciones equivalentes

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

Son los gráficos de comparabilidad de los árboles de teoría del orden . Es decir, sea $T$ un orden parcial tal que para cada $t \in T$ , el conjunto ${s \in T : s < t}$ está bien ordenado por la relación $<$ , y además $T$ posee un elemento mínimo $r$ . Entonces la gráfica de comparabilidad de $T$ es trivialmente perfecta, y toda gráfica trivialmente perfecta puede formarse de esta manera. ^[5]
Son los gráficos que no tienen un gráfico de trayectoria $P 4$ o un gráfico de ciclo $C$ $4$ como subgrafos inducidos . ^[6]
Son los grafos en los que todo subgrafo inducido conexo contiene un vértice universal . ^[7]
Son las gráficas que se pueden representar como gráficas de intervalos para un conjunto de intervalos anidados . Un conjunto de intervalos está anidado si, por cada dos intervalos del conjunto, los dos son disjuntos o uno contiene al otro. ^[8]
Son los grafos que son a la vez cordales y cografos . ^[9] Esto se desprende de la caracterización de los gráficos cordales como los gráficos sin ciclos inducidos de longitud mayor que tres, y de los cografos como los gráficos sin caminos inducidos en cuatro vértices ( $P 4$ ).
Son las gráficas que son a la vez cografías y gráficas de intervalo. ^[9]
Son los gráficos que se pueden formar, a partir de gráficos de un vértice, mediante dos operaciones: unión disjunta de dos gráficos trivialmente perfectos más pequeños y adición de un nuevo vértice adyacente a todos los vértices de un gráfico trivialmente perfecto más pequeño. ^[10] Estas operaciones corresponden, en el bosque subyacente, a formar un nuevo bosque mediante la unión desunida de dos bosques más pequeños y formar un árbol conectando un nuevo nodo raíz a las raíces de todos los árboles de un bosque.
Son los gráficos en los que, para cada arista $uv$ , las vecindades de $u$ y $v$ (incluidas $u$ y $v$ mismas) están anidadas: una vecindad debe ser un subconjunto de la otra. ^[11]
Son los gráficos de permutación definidos a partir de permutaciones ordenables por pila . ^[12]
Son los gráficos con la propiedad de que en cada uno de sus subgrafos inducidos el número de cobertura de camarilla es igual al número de camarillas máximas . ^[13]
Son los gráficos con la propiedad de que en cada uno de sus subgrafos inducidos el número de camarilla es igual al número pseudo-Grundy. ^[13]
Son los grafos con la propiedad de que en cada uno de sus subgrafos inducidos el número cromático es igual al número pseudo-Grundy. ^[13]

Clases relacionadas de gráficos

De las caracterizaciones equivalentes de gráficos trivialmente perfectos se deduce que cada gráfico trivialmente perfecto es también un cografo , un gráfico cordal , un gráfico ptolemaico , un gráfico de intervalo y un gráfico perfecto .

Los gráficos de umbral son exactamente los gráficos que son en sí mismos trivialmente perfectos y los complementos de gráficos trivialmente perfectos (gráficos co-trivialmente perfectos). ^[14]

Los gráficos de molino de viento son trivialmente perfectos.

Reconocimiento

Chu (2008) describe un algoritmo de tiempo lineal simple para reconocer gráficos trivialmente perfectos, basado en la búsqueda lexicográfica de amplitud primero . Siempre que el algoritmo LexBFS elimina un vértice $v$ del primer conjunto en su cola, el algoritmo verifica que todos los vecinos restantes de $v$ pertenezcan al mismo conjunto; de lo contrario, uno de los subgrafos inducidos prohibidos se puede construir a partir de $v$ . Si esta verificación tiene éxito para cada $v$ , entonces la gráfica es trivialmente perfecta. El algoritmo también se puede modificar para probar si un gráfico es el complemento de un gráfico trivialmente perfecto, en tiempo lineal.

Determinar si un gráfico general está $a k$ eliminaciones de bordes de un gráfico trivialmente perfecto es NP-completo , ^[15] manejable con parámetros fijos ^[16] y se puede resolver en tiempo $O (2,45 k (m + n)) .$ ^[17]

Notas

^ Brandstädt, Le & Spinrad (1999), definición 2.6.2, p.34; Golúmbico (1978).
^ Wolk (1962); Wolk (1965).
^ Donnelly e Isaac (1999).
^ Yan, Chen y Chang (1996).
^ Brandstädt, Le & Spinrad (1999), teorema 6.6.1, p. 99; Golumbic (1978), corolario 4.
^ Brandstädt, Le & Spinrad (1999), teorema 6.6.1, p. 99; Golumbic (1978), teorema 2. Wolk (1962) y Wolk (1965) demostraron esto para gráficos de comparabilidad de bosques enraizados.
^ Wolk (1962).
^ Brandstädt, Le y Spinrad (1999), pág. 51.
^ ab Brandstädt, Le y Spinrad (1999), pág. 248; Yan, Chen y Chang (1996), teorema 3.
^ Yan, Chen y Chang (1996); Gurski (2006).
^ Yan, Chen y Chang (1996), teorema 3.
^ Rotem (1981).
^ abc Rubio-Montiel (2015).
^ Brandstädt, Le & Spinrad (1999), teorema 6.6.3, p. 100; Golumbic (1978), corolario 5.
^ Sharan (2002).
^ Cai (1996).
^ Nastos y Gao (2010).

Referencias

Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de gráficos: una encuesta , Monografías de SIAM sobre aplicaciones y matemáticas discretas, ISBN 0-89871-432-X.
Cai, L. (1996), "Tratabilidad de parámetros fijos de problemas de modificación de gráficos para propiedades hereditarias", Information Processing Letters , 58 (4): 171–176, doi :10.1016/0020-0190(96)00050-6.
Chu, Frank Pok Man (2008), "Un tiempo lineal simple que certifica un algoritmo basado en LBFS para reconocer gráficos trivialmente perfectos y sus complementos", Information Processing Letters , 107 (1): 7–12, doi :10.1016/j.ipl. 2007.12.009.
Donnelly, Sam; Isaak, Garth (1999), "Potencias hamiltonianas en gráficos de comparabilidad arborescente y de umbral", Matemáticas discretas , 202 (1–3): 33–44, doi : 10.1016/S0012-365X(98)00346-X
Golumbic, Martin Charles (1978), "Gráficos trivialmente perfectos", Matemáticas discretas , 24 (1): 105–107, doi :10.1016/0012-365X(78)90178-4.
Gurski, Frank (2006), "Caracterizaciones de cografos definidos por operaciones restringidas de ancho de NLC o ancho de camarilla", Matemáticas discretas , 306 (2): 271–277, doi :10.1016/j.disc.2005.11.014.
Nastos, James; Gao, Yong (2010), "Una nueva estrategia de ramificación para problemas de modificación de gráficos parametrizados", en Wu, Weili; Daescu, Ovidiu (eds.), Optimización y aplicaciones combinatorias: cuarta conferencia internacional, COCOA 2010, Kailua-Kona, HI, EE. UU., 18 al 20 de diciembre de 2010, Actas, Parte II , Lecture Notes in Computer Science, vol. 6509, Springer, págs. 332–346, arXiv : 1006.3020 , doi : 10.1007/978-3-642-17461-2_27
Rotem, D. (1981), "Apilar permutaciones ordenables", Matemáticas discretas , 33 (2): 185–196, doi :10.1016/0012-365X(81)90165-5, SEÑOR 0599081.
Rubio-Montiel, C. (2015), "Una nueva caracterización de gráficos trivialmente perfectos", Revista Electrónica de Teoría y Aplicaciones de Grafos , 3 (1): 22–26, doi : 10.5614/ejgta.2015.3.1.3.
Sharan, Roded (2002), "Problemas de modificación de gráficos y sus aplicaciones a la investigación genómica", Tesis doctoral, Universidad de Tel Aviv.
Wolk, ES (1962), "El gráfico de comparabilidad de un árbol", Actas de la Sociedad Matemática Estadounidense , 13 (5 ed.): 789–795, doi : 10.1090/S0002-9939-1962-0172273-0.
Wolk, ES (1965), "Una nota sobre el gráfico de comparabilidad de un árbol", Actas de la American Mathematical Society , 16 (1 ed.): 17–20, doi : 10.1090/S0002-9939-1965-0172274-5.
Yan, Jing-Ho; Chen, Jer-Jeong; Chang, Gerard J. (1996), "Gráficos de cuasi umbral", Matemáticas aplicadas discretas , 69 (3): 247–255, doi :10.1016/0166-218X(96)00094-7.

enlaces externos

"Gráficos trivialmente perfectos", Sistema de Información sobre Clases de Grafos y sus Inclusiones