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 están a una distancia impar (>1) entre sí en el ciclo. [1]
Los grafos fuertemente cordales tienen una caracterización de subgrafo prohibido como los grafos que no contienen un ciclo inducido de longitud mayor que tres o un n-sol ( n ≥ 3) como subgrafo inducido . [2] Un n -sol es un grafo cordal con 2 n vértices, dividido en dos subconjuntos U = { u 1 , u 2 ,...} y W = { w 1 , w 2 ,...}, tales 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 cordal, porque el ciclo u 1 w 1 u 2 w 2 ... no tiene cuerda impar.
Los grafos fuertemente cordales también pueden caracterizarse como los grafos que tienen un ordenamiento de eliminación perfecto fuerte, un ordenamiento de los vértices tal que los vecinos de cualquier vértice que venga más tarde en el ordenamiento forman una camarilla y tal que, para cada i < j < k < l , si el i ésimo vértice en el ordenamiento es adyacente al k ésimo y al l ésimo vértice, y los j ésimo y k ésimo vértices son adyacentes, entonces los j ésimo y l ésimo vértice 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, un grafo 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 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 pueden caracterizarse en términos del número de subgrafos completos en los que participa cada arista. [7] Otra caracterización se da en [8] .
Es posible determinar si un grafo es fuertemente cordal en tiempo polinomial , buscando y eliminando repetidamente un vértice simple. Si este proceso elimina todos los vértices en el grafo, el grafo 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 ordenamiento de eliminación perfecto fuerte de manera más eficiente, en 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 grafos formados a partir de las hojas de un árbol conectando dos hojas por una arista cuando su distancia en el árbol es como máximo k . Una potencia de hoja es un grafo que es una potencia de k -hojas para algún k . Dado que las potencias de grafos fuertemente cordales son fuertemente cordales y los árboles son fuertemente cordales, se deduce que las potencias de hoja son fuertemente cordales. Forman una subclase propia de grafos fuertemente cordales, que a su vez incluye los grafos de clúster como las potencias de 2 hojas. [11] Otra subclase importante de grafos fuertemente cordales son los grafos de intervalo . En [12] se muestra que los grafos de intervalo y la clase más grande de grafos de trayectoria dirigida con raíz son potencias de hoja.
Dado que los grafos fuertemente cordales son tanto grafos cordales como grafos dualmente cordales , varios problemas NP-completos como Conjunto independiente, Clique, Coloración, Cobertura de Clique, Conjunto dominante y Árbol de Steiner se pueden resolver de manera eficiente para grafos fuertemente cordales. El isomorfismo de grafos es isomorfismo-completo para grafos fuertemente cordales. [13] El circuito hamiltoniano sigue siendo NP-completo para grafos fuertemente cordales divididos . [14]