We're still looking for minimal strongly asteroidal graphs, and it's time to move on to the next category B construction. Recall (from last time) that this construction will involve adding a vertex which is adjacent to all three interior vertices; we will call this vertex *v*_{1}.

** Construction B3:** *v*_{1} is adjacent to both *a*_{2} and *a*_{3}, thus creating the path *a*_{2}-*v*_{1}-*a*_{3}, which is *a*_{1}-light. Combining this construction with previous constructions is tricky. Adding constructions A1 or A2 to both *a*_{2} and *a*_{3} creates a copy of the bad aster. However, if we modify these constructions by making the added vertices adjacent to *v*_{1} as well, this creates a minimal graph (if *a*_{2} uses the modified construction, but *a*_{3} does not, then *b*_{2} could be removed to make a smaller strongly asteroidal graph). Similarly, adding construction B1 to both *X*_{2} and *X*_{3} creates a sun, unless we modify the construction by making the added vertices adjacent to *v*_{1}. This modification does not work for construction A3, however, as it creates a copy of the parasol.

If we combine constructions of type A with construction B1, we must still use the modified construction of B1; otherwise, we will create a graph in which *a*_{1} can be removed to make a smaller strongly asteroidal graph. We may, however, use modified or unmodified type A constructions. Graphs 19-21 use only type A constructions with construction B3, and graphs 22-26 use construction B1 at least once.

Construction B3 can also be combined with construction B2. If vertices *u*_{2}, *V*_{2}, and *W*_{2} are added to create the path *a*_{1}-*b*_{1}-*u*_{2}-*v*_{2}-*w*_{2}-*b*_{3}-*a*_{3}, then there is a parasol, unless *v*_{2} and/or *w*_{2} is adjacent to *v*_{1}. If only *w*_{2} is adjacent to *v*_{1}, a chordless cycle is created, and if only *v*_{2} is adjacent to *v*_{1}, *a*_{1} and *b*_{1} can be removed to make a smaller strongly asteroidal graph, regardless of the construction added to *a*_{3} (which must be a type A construction, because B2 does not combine with B1, and applying B2 twice will produce a copy of graph 18). If both are adjacent, then removing *a*_{1} and *b*_{1} leaves a graph equivalent to combining B3 with B1 (with *u*_{2} and *v*_{1} standing in for *a*_{1} and *b*_{1}). So, *u*_{2}, *v*_{2}, and *w*_{2} must all be adjacent to *v*_{1}. Then, either a modified or unmodified type A construction can be added to *a*_{3}, producing graphs 27-30.

If construction B3 is applied twice, with vertex *v*_{2} adjacent to *a*_{1} and *a*_{3} (as well as each vertex *b _{i}*), then

*v*

_{1}and

*v*

_{2}must be adjacent to avoid chordless cycles. Adding construction A1 or A2 to

*a*

_{3}will produce a copy of graph 9, so we must add a type B construction to

*X*

_{3}to obtain a minimal graph. Applying B3 a third time will result in a 3-sun, but both B1 and B2 will work, as long as all of the added vertices are adjacent to both

*v*

_{1}and

*v*

_{2}. Construction B1 produces graph 31, and construction B2 produces graph 32.

Next time, we face the horror that is construction B4. For those who couldn't give a rip about all of this graph theory, there will be trivia posted tonight or tomorrow.

## No comments:

Post a Comment