Un grafo no dirigido G se llama estrictamente cordal si es cordal y cualquier ciclo de longitud par ( ) en G tiene una cuerda impar , es decir, una arista que conecta dos vértices del ciclo a una distancia impar (>1) entre sí [1] .
Los grafos estrictamente cordales son descritos por grafos prohibidos como grafos que no contienen un ciclo generado de más de tres longitudes o un n -sun ( ) como un subgrafo generado [2] [3] [4] . El n -Sun es un grafo cordal con 2n vértices divididos en dos subconjuntos y tal que cada vértice w i de W tiene exactamente dos vecinos, u i y . n -Sol no puede ser estrictamente cordal, ya que el ciclo ... no tiene acordes impares.
Los grafos estrictamente cordales se pueden describir como grafos que tienen un orden de eliminación perfecto estricto, un orden de vértices tal que los vecinos de cualquier vértice que viene después en orden forman una camarilla , y tal que para cualquier , si el i -ésimo vértice en el orden es adyacente a los vértices k -ésimo y l -ésimo , y los vértices j -ésimo y k - ésimo son adyacentes, entonces ambos vértices j - ésimo y l - ésimo deben ser adyacentes [3] [5] .
Un grafo es estrictamente cordal si y solo si alguno de sus subgrafos generados tiene un vértice simple, es decir, un vértice cuyos vecinos están ordenados linealmente por orden de inclusión [3] [6] . Además, un grafo es estrictamente cordal si y sólo si es cordal y cualquier ciclo de longitud cinco o más tiene un triángulo de 2 cuerdas, es decir, un triángulo formado por dos cuerdas y una arista del ciclo [7] .
Un grafo es estrictamente cordal si y solo si alguno de sus subgrafos generados es un grafo cordal dual [8] .
Los grafos estrictamente cordales se pueden describir en términos del número de subgrafos completos a los que pertenece una arista [9] . Otra descripción se da en el artículo de De Caria y McKee [10] .
Es posible determinar si un gráfico es estrictamente cordal en tiempo polinomial buscando y eliminando repetidamente un vértice simple. Si este proceso elimina todos los vértices del grafo, entonces el grafo debe ser estrictamente cordal. De lo contrario, el proceso no encuentra un subgrafo sin vértice simple, y en este caso el grafo original no puede ser estrictamente cordal. Para un grafo estrictamente cordal, el orden en el que se eliminan los vértices en este proceso se denomina orden de eliminación perfecto estricto [3] .
Se conocen algoritmos alternativos que pueden determinar si un grafo es estrictamente cordal y, de ser así, construir un orden de eliminación perfecto estricto de manera más eficiente, en el tiempo, para un grafo con n vértices y m aristas [11] [12] [13] .
Una subclase importante (basada en la filogenia ) es la clase de k - grados de hoja , es decir, gráficos formados a partir de las hojas de un árbol al conectar dos hojas con un borde si la distancia en el árbol no excede k . Un grado de hoja es un gráfico que es un k -grado de hoja para alguna k . Dado que los grados de los grafos estrictamente cordales son estrictamente cordales y los árboles son estrictamente cordales, se deduce que los grados de las hojas son estrictamente cordales. Forman su propia subclase de grafos fuertemente cordales, que a su vez incluye grafos de conglomerados como potencias de 2 hojas [14] . Otra subclase importante de grafos estrictamente cordales son los grafos de intervalo . Branstedt, Hudt, Mancini y Wagner [15] demostraron que los gráficos de intervalo y una clase más grande de caminos de raíz dirigidos son poderes de hoja.
Debido a que los gráficos fuertemente cordales son tanto cordales como dualmente cordales , varios problemas NP-completos como el problema del conjunto independiente , el problema de la camarilla , la coloración , el problema de cobertura de la camarilla , el conjunto dominante y el problema del árbol mínimo de Steiner se pueden resolver de manera eficiente para gráficos fuertemente cordales. El problema de isomorfismo de grafos es GI-completo [16] para grafos estrictamente cordales [17] . La búsqueda de ciclos hamiltonianos sigue siendo un problema NP-completo para gráficos de división estrictamente cordales [18] .