In the final post on strongly asteroidal graphs, we look at asteroidal graphs other than *S*_{3}; namely, graphs *III _{n}* (for

*n*> 2) and

*IV*(for

_{n}*n*> 1). Fortunately, changing these graphs into minimal strongly asteroidal graphs is not nearly as complicated as it was for

*S*

_{3}, for two reasons. The first, and most important, is that there is only one potential middle vertex (

*a*

_{1}) 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*_{1} has three consecutive *a*_{1}-heavy vertices *x-y-z*, with *a*_{1}-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*_{1} as the strongly asteroidal triple). If, on the other hand, we attempt to place a single *a*_{1}-light vertex adjacent to *x*, *y*, and *z*, then this creates a chordless cycle with *a*_{1}. Therefore, category B constructions are minimal only if *X*_{1} 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*_{2} will create a *k*-sun, where *k* is 3, 4, or 5, depending on the adjacencies between the *a*_{1}-light vertices and the neighbors of *a*_{1}.

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*_{2}, 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*

_{1}; 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*

_{1}might create a new sAT, in which a1 becomes part of a

*v*-light path between

*a*

_{2}and

*a*

_{3}. This construction can only work for

*n*> 2, because

*v*cannot be adjacent to a neighbor of

*a*

_{2}or

*a*

_{3}. However, for

*n*> 3, this construction will create a copy of graph

*II*. The construction does work for graph

*IV*

_{3}, 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:

Post a Comment