En el área matemática de la teoría de grafos , un grafo no dirigido G es fuertemente cordal si es un grafo cordal y cada ciclo de longitud par (≥ 6) en G tiene una cuerda impar , es decir, una arista que conecta dos vértices que son impares. distancia (> 1) entre sí en el ciclo. [1]
Caracterizaciones
Los grafos fuertemente cordales tienen una caracterización de subgrafo prohibido como los grafos que no contienen un ciclo inducido de longitud mayor a tres o un n- sol ( n ≥ 3) como subgrafo inducido . [2] Un n -sun es un grafo cordal con 2 n vértices, dividido en dos subconjuntos U = { u 1 , u 2 , ...} y W = { w 1 , w 2 , ...}, tal que cada vértice w i en W tiene exactamente dos vecinos, u i y u ( i + 1) mod n . Un n- sol no puede ser fuertemente acorde, porque el ciclo u 1 w 1 u 2 w 2 ... no tiene un acorde impar.
Los gráficos fuertemente cordales también se pueden caracterizar como los gráficos que tienen un fuerte orden de eliminación perfecto, un orden de los vértices tal que los vecinos de cualquier vértice que venga más adelante en el orden formen una camarilla y tal que, para cada i < j < k < l , si el i- ésimo vértice en el ordenamiento es adyacente a los vértices k- ésimo y l- ésimo, y los vértices j- ésimo y k- ésimo son adyacentes, entonces los vértices j- ésimo y l- ésimo también deben ser adyacentes. [3]
Un grafo es fuertemente cordal si y solo si cada uno de sus subgrafos inducidos tiene un vértice simple, un vértice cuyos vecinos tienen vecindarios que están ordenados linealmente por inclusión. [4] Además, una gráfica es fuertemente cordal si y solo si es cordal y cada ciclo de longitud cinco o más tiene un triángulo de 2 cuerdas, un triángulo formado por dos cuerdas y un borde del ciclo. [5]
Un grafo es fuertemente cordal si y solo si cada uno de sus subgrafos inducidos es un grafo dualmente cordal . [6]
Los grafos fuertemente cordales también pueden caracterizarse en términos del número de subgrafos completos en los que participa cada borde. [7] Sin embargo, se da otra caracterización en. [8]
Reconocimiento
Es posible determinar si una gráfica es fuertemente cordal en el tiempo polinomial , buscando y eliminando repetidamente un vértice simple. Si este proceso elimina todos los vértices del gráfico, el gráfico debe ser fuertemente cordal; de lo contrario, si este proceso encuentra un subgrafo sin más vértices simples, el grafo original no puede ser fuertemente cordal. Para un grafo fuertemente cordal, el orden en el que se eliminan los vértices mediante este proceso es un orden de eliminación perfecto fuerte. [9]
Ahora se conocen algoritmos alternativos que pueden determinar si un gráfico es fuertemente cordal y, de ser así, construir un orden de eliminación perfecto fuerte de manera más eficiente, en el tiempo O (min ( n 2 , ( n + m ) log n )) para un gráfico con n vértices y m aristas. [10]
Subclases
Una subclase importante (basada en la filogenia ) es la clase de k - poderes de las hojas , los gráficos formados a partir de las hojas de un árbol al conectar dos hojas por un borde cuando su distancia en el árbol es como máximo k . Una potencia de hoja es una gráfica que es una potencia de k hojas para algunos k . Dado que los poderes de los gráficos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que los poderes de las hojas son fuertemente cordales. Forman una subclase adecuada de gráficos fuertemente cordales, que a su vez incluyen los gráficos de agrupamiento como potencias de 2 hojas. [11] Otra subclase importante de gráficos fuertemente cordales son los gráficos de intervalo . En [12] se muestra que los gráficos de intervalo y la clase más grande de gráficos de trayectoria dirigida con raíces son poderes de hoja.
Problemas algorítmicos
Dado que los gráficos son muy acordes ambos gráficos de cuerdas y gráficos doblemente cordales , diversos problemas NP-completos, como Independiente grupo, banda, colorear, cubierta camarilla, dominando Conjunto, y el árbol de Steiner se pueden resolver de manera eficiente para gráficos fuertemente cordales. El isomorfismo de grafo es isomorfismo completo para grafos fuertemente cordales. [13] El circuito hamiltoniano sigue siendo NP-completo para gráficos divididos fuertemente cordales . [14]
Notas
- ^ Brandstädt, Le & Spinrad (1999) , Definición 3.4.1, p. 43.
- ^ Chang (1982) ; Farber (1983) ; Brandstädt, Le y Spinrad (1999) , Teorema 7.2.1, pág. 112.
- ^ Farber (1983) ; Brandstädt, Le y Spinrad (1999) , Teorema 5.5.1, pág. 77.
- ^ Farber (1983) ; Brandstädt, Le y Spinrad (1999) , Teorema 5.5.2, pág. 78.
- ^ Dahlhaus, Manuel y Miller (1998) .
- ^ Brandstädt y col. (1998) , Corolario 3, pág. 444
- ^ McKee (1999)
- ^ De Caria y McKee (2014)
- ^ Farber (1983) .
- ^ Lubiw (1987) ; Paige y Tarjan (1987) ; Spinrad (1993) .
- ^ Nishimura, Ragde y Thilikos (2002)
- ^ Brandstädt y col. (2010)
- ^ Uehara, Toda y Nagoya (2005)
- ↑ Müller (1996)
Referencias
- Brandstädt, Andreas ; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi : 10.1137 / s0895480193253415.
- Brandstädt, Andreas ; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Los gráficos de trayectoria dirigidos con raíces son poderes de hoja", Matemáticas discretas , 310 (4): 897–910, doi : 10.1016 / j.disc.2009.10.006.
- Brandstädt, Andreas ; Le, Van Bang (2006), "Estructura y reconocimiento de tiempo lineal de poderes de 3 hojas", Information Processing Letters , 98 (4): 133-138, doi : 10.1016 / j.ipl.2006.01.004.
- Brandstädt, Andreas ; Le, Van Bang; Sritharan, R. (2008), "Estructura y reconocimiento de tiempo lineal de potencias de 4 hojas", ACM Transactions on Algorithms , 5 : Artículo 11, doi : 10.1145 / 1435375.1435386.
- 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.
- Chang, GJ (1982), Dominación K y problemas de cobertura de gráficos , Ph.D. tesis, Universidad de Cornell.
- Dahlhaus, E .; Manuel, PD; Miller, M. (1998), "Una caracterización de grafos fuertemente cordales", Matemáticas discretas , 187 (1-3): 269-271, doi : 10.1016 / S0012-365X (97) 00268-9.
- De Caria, P .; McKee, TA (2014), "Maxclique y caracterizaciones de disco unitario de grafos fuertemente cordales", Discussiones Mathematicae Graph Theory , 34 (3): 593–602, doi : 10.7151 / dmgt.1757.
- Farber, M. (1983), "Caracterizaciones de grafos fuertemente cordales", Matemáticas discretas , 43 (2-3): 173-189, doi : 10.1016 / 0012-365X (83) 90154-1.
- Lubiw, A. (1987), "Doble ordenación léxica de matrices", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137 / 0216057.
- McKee, TA (1999), "Una nueva caracterización de grafos fuertemente cordales", Matemáticas discretas , 205 (1–3): 245–247, doi : 10.1016 / S0012-365X (99) 00107-7.
- Müller, H. (1996), "Circuitos hamiltonianos en gráficos bipartitos cordales", Matemáticas discretas , 156 (1-3): 291-298, doi : 10.1016 / 0012-365x (95) 00057-4.
- Nishimura, N .; Ragde, P .; Thilikos, DM (2002), "Sobre potencias gráficas para árboles etiquetados con hojas", Journal of Algorithms , 42 : 69–108, doi : 10.1006 / jagm.2001.1195.
- Paige, R .; Tarjan, RE (1987), "Tres algoritmos de refinamiento de particiones", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137 / 0216062.
- Rautenbach, D. (2006), "Algunas observaciones sobre las raíces de las hojas", Matemáticas discretas , 306 (13): 1456–1461, doi : 10.1016 / j.disc.2006.03.030.
- Spinrad, J. (1993), "Ordenamiento doblemente léxico de matrices densas 0-1", Information Processing Letters , 45 (2): 229-235, doi : 10.1016 / 0020-0190 (93) 90209-R.
- Uehara, R .; Toda, S .; Nagoya, T. (2005), "Completitud del isomorfismo del grafo para grafos bipartitos cordales y fuertemente cordales", Matemáticas aplicadas discretas , 145 (3): 479–482, doi : 10.1016 / j.dam.2004.06.008.