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 S3, 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 c1 is added which is adjacent to a1, b1, b2 and b3, and a category B construction is added to the path X1. In addition, edges are added between b1 and every vertex in the category B construction. The modified category B construction still creates an a1-light path, because there will not be consecutive vertices adjacent to c1. Equivalently, this can be thought of as adding a regular category B construction, and then making c1 adjacent to every vertex except a2 and a3. 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 b1. 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 c1 is adjacent to b2 and b3, removing b1 from construction Cn will make a graph isomorphic to one with construction Bn applied. Therefore, in order to create a new minimal sAT, it is necessary for b1 to be part of another light path.
In construction C1, this means that a category B or C construction must be applied to either a2 or a3, but in constructions C2 and C4, b1 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 X2, and applying constructions A1, A2, or B1 to a3 (or X3); 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 c1 and c2 are not adjacent to each other, then the vertices v1 and v2 become unnecessary. If c1 and c2 are adjacent, but v1 and c2 are not, then v2 is still unnecessary. Finally, we can allow c1 to be adjacent to c2 and v2, and c2 to be additionally adjacent to v1.
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 c1, c2, and c3 are adjacent to each other, and only one additional vertex v is necessary; it is adjacent to b1, b2, and b3. This creates graph 51. Other modifications of the adjacencies between c1, c2, c3, and v1, v2, and v3 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 b1 and the B2 portion of the construction create a2- and a3-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 b1, the addition of vertex c1 is unnecessary to create an a1-light path. Finally, construction C4, like construction C2, contains an a2-light path. Category B constructions that modify the path X3 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 a3 to make graphs 53 and 54.
These are the final minimal sATs that arise from the graph S3. 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