Strongly chordal graph

[2] An n-sun is a chordal graph with 2n vertices, partitioned into two subsets U = {u1, u2,...} and W = {w1, w2,...}, such that each vertex wi in W has exactly two neighbors, ui and u(i + 1) mod n. An n-sun cannot be strongly chordal, because the cycle u1w1u2w2... has no odd chord.

[6] Strongly chordal graphs may also be characterized in terms of the number of complete subgraphs each edge participates in.

[8] It is possible to determine whether a graph is strongly chordal in polynomial time, by repeatedly searching for and removing a simple vertex.

[9] Alternative algorithms are now known that can determine whether a graph is strongly chordal and, if so, construct a strong perfect elimination ordering more efficiently, in time O(min(n2, (n + m) log n)) for a graph with n vertices and m edges.

[13] Hamiltonian Circuit remains NP-complete for strongly chordal split graphs.

In the first graph, the 8-cycle has odd edges 3-6 and 2-7, and the 6-cycles each also have one of those two edges as an odd edge. In the second graph, the two red edges need to be added, one so that the 8-cycle has an odd edge, and the other to make an odd chord for the 6-cycle formed by the newly inserted edge.