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]
Los gráficos fuertemente cordales tienen una caracterización de subgrafo prohibido como los gráficos que no contienen un ciclo inducido de longitud mayor que tres o un n-sol ( n ≥ 3) como un 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 wi en W tiene exactamente dos vecinos, u i y u ( i + 1) mod n . Un n -sun no puede ser fuertemente cordal, porque el ciclo u 1 w 1 u 2 w 2 ... no tiene cuerda impar.
Los gráficos fuertemente cordales también se pueden caracterizar como gráficos que tienen un fuerte orden de eliminación perfecta, un orden de los vértices tal que los vecinos de cualquier vértice que vienen más tarde en el orden forman una camarilla y tal que, para cada i < j < k < l , si el vértice i en el ordenamiento es adyacente a los vértices k y l , y los vértices j y k son adyacentes, entonces los vértices j y l también deben ser adyacentes. [3]
Un grafo es fuertemente cordal si y sólo si cada uno de sus subgrafos inducidos tiene un vértice simple, un vértice cuyos vecinos tienen vecindades que están ordenadas linealmente por inclusión. [4] Además, un grafo es fuertemente cordal si y sólo 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 una arista del ciclo. [5]
Un grafo es fuertemente cordal si y sólo si cada uno de sus subgrafos inducidos es un grafo dualmente cordal . [6]
Los grafos fuertemente cordales también se pueden caracterizar en términos del número de subgrafos completos en los que participa cada borde. [7] Se proporciona otra caracterización más. [8]
Es posible determinar si un gráfico es fuertemente cordal en 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 gráfico original no puede ser fuertemente cordal. Para un gráfico 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]
Una subclase importante (basada en la filogenia ) es la clase de potencias de k - hojas , los gráficos formados a partir de las hojas de un árbol conectando dos hojas por un borde cuando su distancia en el árbol es como máximo k . Una potencia de hoja es un gráfico que es una k -potencia de hoja para algunos k . Dado que las potencias de los grafos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que las potencias de las hojas son fuertemente cordales. Forman una subclase adecuada de gráficos fuertemente cordales, que a su vez incluye los gráficos de grupo 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 amplia de gráficos de trayectoria dirigida con raíz son potencias de hoja.
Dado que los gráficos fuertemente cordales son a la vez gráficos cordales y gráficos dualmente cordales , varios problemas NP-completos, como conjunto independiente, camarilla, coloración, cubierta de camarilla, conjunto dominante y árbol de Steiner, se pueden resolver de manera eficiente para gráficos fuertemente cordales. El isomorfismo de grafos es isomorfismo completo para grafos fuertemente cordales. [13] El circuito hamiltoniano sigue siendo NP completo para gráficos divididos fuertemente cordales . [14]