Welcome to the penultimate post on strongly asteroidal graphs. We've seen category A constructions, in which a neighbor is added to one of the asteroidal vertices of *S*_{3}, and category B constructions, which modify the path between two asteroidal vertices. Today, we will look at category C constructions, which do both.

In a category C construction, a vertex *c*_{1} is added which is adjacent to *a*_{1}, *b*_{1}, *b*_{2} and *b*_{3}, and a category B construction is added to the path *X*_{1}. In addition, edges are added between *b*_{1} and *every* vertex in the category B construction. The modified category B construction still creates an *a*_{1}-light path, because there will not be consecutive vertices adjacent to *c*_{1}. Equivalently, this can be thought of as adding a regular category B construction, and then making *c*_{1} adjacent to every vertex except *a*_{2} and *a*_{3}. However, it is more convenient, in terms of adding later constructions, to modify the category B construction so that all of the vertices are adjacent to *b*_{1}. Each category B construction has a corresponding category C construction, so the category C constructions can intuitively be labeled C1-C4. The constructions are in the figure below.

Because *c*_{1} is adjacent to *b*_{2} and *b*_{3}, removing *b*_{1} from construction C*n* will make a graph isomorphic to one with construction B*n* applied. Therefore, in order to create a new minimal sAT, it is necessary for *b*_{1} to be part of another light path.

In construction C1, this means that a category B or C construction must be applied to either *a*_{2} or *a*_{3}, but in constructions C2 and C4, *b*_{1} is already part of at least one light path, which includes one vertex from the category B construction (it is difficult to see, but these paths are colored red and blue in the diagram).

Construction C1 does not combine with construction A3 (a parasol is created), but we do get new minimal sATs by applying construction B1 or B2 to the path *X*_{2}, and applying constructions A1, A2, or B1 to *a*_{3} (or *X*_{3}); these are graphs 37-41. In addition, construction C1 can be combined with constructions B1 and B3 to create graph 42; construction B4 can be used instead of B3 to create graph 44, which we'll get to in a second. In the above figure, note that several of these graphs have been rotated/reflected.

Applying C1 a second time can lead to several new graphs. If the vertices *c*_{1} and *c*_{2} are not adjacent to each other, then the vertices *v*_{1} and *v*_{2} become unnecessary. If *c*_{1} and *c*_{2} are adjacent, but *v*_{1} and *c*_{2} are not, then *v*_{2} is still unnecessary. Finally, we can allow *c*_{1} to be adjacent to *c*_{2} and *v*_{2}, and *c*_{2} to be additionally adjacent to *v*_{1}.

Adding construction B1 or B2 to any of these combinations, or B3 to either of the latter two combinations, will create a new minimal strongly asteroidal graph. Graphs 43-45 are those that occur using construction B2, graphs 46-48 use B2, and graphs 49 and 50 use B3. The category A constructions and construction B4 do not lead to new minimal graphs.

Finally, there is one way to apply construction C1 to all three asteroidal vertices. The vertices *c*_{1}, *c*_{2}, and *c*_{3} are adjacent to each other, and only one additional vertex *v* is necessary; it is adjacent to *b*_{1}, *b*_{2}, and *b*_{3}. This creates graph 51. Other modifications of the adjacencies between *c*_{1}, *c*_{2}, *c*_{3}, and *v*_{1}, *v*_{2}, and *v*_{3} do not create new minimal graphs; the most common result is a 3-sun.

Only a few minimal graphs arise from the other category C constructions. Construction C2 actually is a minimal sAT by itself, as the adjacencies between *b*_{1} and the B2 portion of the construction create *a*_{2}- and *a*_{3}-light paths. This is graph 52. Construction C3 does not lead to any new minimal graphs; because the only added vertex in construction B3 is already adjacent to *b*_{1}, the addition of vertex *c*_{1} is unnecessary to create an *a*_{1}-light path. Finally, construction C4, like construction C2, contains an *a*_{2}-light path. Category B constructions that modify the path *X*_{3} do not combine with this, for the same reason they do not combine with construction B4. However, constructions A1 and A2 can be applied to *a*_{3} to make graphs 53 and 54.

These are the final minimal sATs that arise from the graph *S*_{3}. Next time, we'll finish up by looking at the infinite families of asteroidal graphs, and seeing how to modify those to create strongly asteroidal graphs.

## No comments:

Post a Comment