I've mentioned chordal graphs a few times already. Today, we'll look at strongly chordal graphs. If a graph has a cycle with *k* vertices in it (where *k* > 3), and we label the vertices 1, 2, ..., *k*, consecutively (so 1 is adjacent to 2 and to *k*), then if vertices *i* and *j* are adjacent, and *i* and *j* differ by more than one (and aren't 1 and *k*), then the edge between *i* and *j* is a chord. If the difference between *i* and *j* is odd (even), then this edge is an *odd (even) chord*. A *strongly chordal* graph is a graph in which every cycle of at least four vertices has a chord (which makes it chordal), and every cycle of at least six vertices has an odd chord.

Strongly chordal graphs are equivalently defined as graphs which have a *strong elimination ordering** *(the definition begins at the bottom of page 76 in the linked text). Farber defined the strong elimination ordering in a 1983 paper, and also showed that strongly chordal graphs are precisely the graphs which are chordal and *sun-free*. A k-*sun* is an even cycle, with at 2*k* vertices (*k *> 2), in which the vertices can be numbered such that the even vertices have no additional edges (beyond the two you'd expect), and the odd vertices form a *clique*. If the odd vertices form a chordal graph, but not a complete graph, then the cycle is an *incomplete sun*. Some graph theorists prefer to call the latter graph a sun, and the former a *complete sun*. Every incomplete sun contains a *k-*sun, so the difference is semantic. Below are *S*_{3} (again) and *S*_{4}.

As was mentioned yesterday, *S*_{3} contains a sAT. So does *S*_{4}, and, in fact, every sun. This is not a surprise; Monma, Reed, and Trotter showed in their original paper that co-TT graphs are strongly chordal (by finding a strong elimination ordering). In my dissertation, I showed that the *k*-suns are minimal forbidden subgraphs; removing any vertex from a *k*-sun results in a co-TT graph. If we label the vertices of a *k*-sun as described above, any three of the even vertices form a sAT; simply moving along the cycle from one vertex to the next gives a *light* path, as opposed to a *heavy* path, which I mentioned yesterday, and will talk about tomorrow.

## No comments:

Post a Comment