Wednesday, November 4, 2009

Lesson 12: Why Bigger Isn't Better

In the final post on strongly asteroidal graphs, we look at asteroidal graphs other than S3; namely, graphs IIIn (for n > 2) and IVn (for n > 1). Fortunately, changing these graphs into minimal strongly asteroidal graphs is not nearly as complicated as it was for S3, for two reasons. The first, and most important, is that there is only one potential middle vertex (a1) in the asteroidal triple, so only one construction need be applied. The second reason is that applying the category B constructions (and, by extension, category C constructions) fails to produce a light path. Here's why:

Suppose that X1 has three consecutive a1-heavy vertices x-y-z, with a1-light vertices u between x and y, and v between y and z. If x and z are not adjacent, then this creates a copy of graph II (with u, v, and a1 as the strongly asteroidal triple). If, on the other hand, we attempt to place a single a1-light vertex adjacent to x, y, and z, then this creates a chordless cycle with a1. Therefore, category B constructions are minimal only if X1 contains just two consecutive a1-heavy vertices, so we need not apply them when n > 2. Further, applying any category B construction to graph IV2 will create a k-sun, where k is 3, 4, or 5, depending on the adjacencies between the a1-light vertices and the neighbors of a1.

This means we only need to focus on the category A constructions. Applying construction A1 to any of these graphs creates a copy of graph I, except in the case of graph IV2, in which case we get graph 9. Applying construction A3 to any of these graphs results in a copy of graph II. Only construction A2 creates new minimal graphs. For the graphs in family IVn, the added vertex must be adjacent to both neighbors of a1; if it is only adjacent to one of the neighbors, a copy of graph II is created. This gives us two families of minimal strongly asteroidal graphs; these are 55n and 56n below.

There is one final construction to consider for graph IVn; adding a pendant vertex v somewhere along the path X1 might create a new sAT, in which a1 becomes part of a v-light path between a2 and a3. This construction can only work for n > 2, because v cannot be adjacent to a neighbor of a2 or a3. However, for n > 3, this construction will create a copy of graph II. The construction does work for graph IV3, but the graph it creates is graph 43. We are out of ways to modify the minimal asteroidal graphs, so we conclude that we have, at long last, found all of the minimal strongly asteroidal graphs.

We have also, at long last, concluded this topic. The math talk will continue, though. Next up is some probability theory, as I examine a dice game.

No comments: