It has been two months since I posted lesson 9. There are a few reasons for the delay, but one reason is that the final category B construction has been a thorn in my side for months. I originally thought that it gave rise to no new minimal graphs. Then, I found one new sAT, then two, then three, then went back down to two, and so on. Every time I thought that I had thoroughly examined the construction, another combination occurred to me. Over the last month, I have examined each combination of constructions that included B4, one by one, and have officially convinced myself whether each combination does or does not produce a new minimal sAT.

** Construction B4:** The vertex *v*_{1} is adjacent to *a*_{2}. In addition, a vertex *u*_{1} is added, which is adjacent to *v*_{1} and *b*_{3}. This creates the *a*_{1}-light path *a*_{2}-*v*_{1}-*u*_{1}-*b*_{3}-*a*_{3}.

The great difficulty in construction B4 lies in the fact that it lacks symmetry. With the previous category B constructions, adding a construction to *a*_{2} was no different than adding it to *a*_{3}. For example, two combinations produce graph 16. With B4, this is no longer the case; when we apply other constructions, it is important whether they are applied to *a*_{2} or *a*_{3}. In addition, if we apply B4 a second time, it matters which of the asteroidal vertices is adjacent to the vertex *v*_{2}.

One important thing to note is that applying this construction, and then removing the vertex *b*_{2}, is equivalent to just applying construction B1. To create a minimal sAT, the other two constructions must be applied in such a way that either *b*_{2} is part of every *a*_{3}-light path, or that every *a*_{2}-light path would be heavy if *b*_{2} were removed. This means that the construction applied to *a*_{2} cannot be a category A construction, or construction B3. In addition, applying construction B1 or B2 to the path *X*_{3} creates either a graph in which *b*_{2} can be removed, or one with a chordless cycle. Applying construction A3 to either *a*_{2} or *a*_{3} creates a copy of the parasol.

If we apply a category B construction to the path *X*_{2}, the added vertices must be adjacent to *v*_{1}, in order to avoid suns and parasols. Construction B1 will create new minimal graphs when constructions A1, A2, or B3 are applied to a3; these are graphs 33-35 below. Construction B2 results in a graph in which *u*_{1} is removable; in fact, it creates a category C construction, which we'll get to next time.

Attempting to apply B4 a second time creates problems. If it is applied to the path *X*_{2}, we must decide whether the vertex *v*_{2} is adajcent to *a*_{1} or *a*_{3}. If it is adjacent to *a*_{1}, then we do not get a minimal sAT, as (depending on the adjacencies) the resulting graph will contain suns, chordless cycles, or a category C construction. Suppose, then, that *v*_{2} is adjacent to *a*_{3}. Then applying a category A construction to *a*_{3}, or construction B3 to the path *X*_{3} is no longer possible (for the same reasons they could not be applied to *a*_{2} or *X*_{2} earlier). However, allowing *v*_{1} to be adjacent to *u*_{2} and *v*_{2}, and *v*_{2} to additionally be adjacent to *u*_{1}, creates the *a*_{3}-light path *a*_{1}-*b*_{1}-*u*_{2}-*v*_{1}-*a*_{2}, while also preventing the removal of *b*_{2} or *b*_{3}. This is, therefore, a minimal sAT; this is graph 36 at left.

Applying construction B4 to path X3 does not create new strongly asteroidal graphs; in any strongly chordal graph where this is applied, either a1 or b2 will be removable.

Next time, I'll start on the category C constructions. It's all downhill from here, kids. Two more posts max, and then we can move to a new topic.

## No comments:

Post a Comment