Lesson 12: Why Bigger Isn't Better

In the final post on strongly asteroidal graphs, we look at asteroidal graphs other than S₃; namely, graphs III_n (for n > 2) and IV_n (for n > 1). Fortunately, changing these graphs into minimal strongly asteroidal graphs is not nearly as complicated as it was for S₃, for two reasons. The first, and most important, is that there is only one potential middle vertex (a₁) 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 X₁ has three consecutive a₁-heavy vertices x-y-z, with a₁-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 a₁ as the strongly asteroidal triple). If, on the other hand, we attempt to place a single a₁-light vertex adjacent to x, y, and z, then this creates a chordless cycle with a₁. Therefore, category B constructions are minimal only if X₁ contains just two consecutive a1-heavy vertices, so we need not apply them when n > 2. Further, applying any category B construction to graph IV₂ will create a k-sun, where k is 3, 4, or 5, depending on the adjacencies between the a₁-light vertices and the neighbors of a₁.

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 IV₂, 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 IV_n, the added vertex must be adjacent to both neighbors of a₁; 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 55_n and 56_n below.

There is one final construction to consider for graph IV_n; adding a pendant vertex v somewhere along the path X₁ might create a new sAT, in which a1 becomes part of a v-light path between a₂ and a₃. This construction can only work for n > 2, because v cannot be adjacent to a neighbor of a₂ or a₃. However, for n > 3, this construction will create a copy of graph II. The construction does work for graph IV₃, 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.