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 v1 is adjacent to a2. In addition, a vertex u1 is added, which is adjacent to v1 and b3. This creates the a1-light path a2-v1-u1-b3-a3.
The great difficulty in construction B4 lies in the fact that it lacks symmetry. With the previous category B constructions, adding a construction to a2 was no different than adding it to a3. 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 a2 or a3. In addition, if we apply B4 a second time, it matters which of the asteroidal vertices is adjacent to the vertex v2.
One important thing to note is that applying this construction, and then removing the vertex b2, 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 b2 is part of every a3-light path, or that every a2-light path would be heavy if b2 were removed. This means that the construction applied to a2 cannot be a category A construction, or construction B3. In addition, applying construction B1 or B2 to the path X3 creates either a graph in which b2 can be removed, or one with a chordless cycle. Applying construction A3 to either a2 or a3 creates a copy of the parasol.
If we apply a category B construction to the path X2, the added vertices must be adjacent to v1, 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 u1 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 X2, we must decide whether the vertex v2 is adajcent to a1 or a3. If it is adjacent to a1, 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 v2 is adjacent to a3. Then applying a category A construction to a3, or construction B3 to the path X3 is no longer possible (for the same reasons they could not be applied to a2 or X2 earlier). However, allowing v1 to be adjacent to u2 and v2, and v2 to additionally be adjacent to u1, creates the a3-light path a1-b1-u2-v1-a2, while also preventing the removal of b2 or b3. 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