Welcome to the latest installment in the continuing struggle to find minimal strongly asteroidal graphs. We are creating these graphs by adding vertices to the minimal asteroidal graphs, as discussed in lesson 5. Specifically, we're adding these vertices to the graph *S*_{3}; see lesson 7 for the terminology I use in referring to the various vertices in that graph. Last time, we looked at category A constructions, which add a neighbor to the vertex *a _{i}*, in order to prevent it from being a middle vertex. In today's lesson, we'll start to look at the category B constructions, which involve adding vertices to the path

*X*to make it

_{i}*a*-light. The number of vertices we can add is limited somewhat; I'll spare the details, but an

_{i}*a*-light path in a minimal sAT will have a maximum of three

_{i}*a*-heavy vertices. This is a small result, but it is important, because it a) means that there are only a small number of constructions in this category, and b) it places an upper bound on the length of the

_{i}*a*-light paths, which in turn places an upper bound on the order of the minimal graphs we can get by adding vertices to

_{i}*S*

_{3}, which means the number of sporadic cases is finite. Before we begin, recall that, when a construction of category B (or C) is applied, the added vertices can be adjacent to the added vertices from other constructions from category B or C. This adds a level of complexity not found in the category A constructions.

** Construction B1:** a single vertex *u*_{1} is added, adjacent to *b*_{2} and *b*_{3}. This creates an *a*_{1}-light path, and thus prevents *a*_{1} from being a middle vertex. If this construction is applied twice, say by adding a vertex *u*_{2} to prevent *a*_{2} from being the middle vertex, then the new vertices cannot be adjacent: this would create a chordless cycle *u*_{1}−*u*_{2}−*b*_{1}−*b*_{2}−*u*_{1}, and adding a chord between *b*_{i }and *u _{i}* (where

*i*is 1 or 2) would make

*u*

_{i}*a*-heavy, defeating the purpose of the construction. Then B1 cannot be applied to all three paths, as this will create a 3-sun. It may be applied up to twice, though, in combination with constructions A1 or A2, to produce graphs 10-14. Applying constructions A3 and B1 together produces a copy of the parasol, so this is not minimal.

_{i}

Starting with construction B2, the remaining constructions all involve adding one or more vertices which are adjacent to all three interior vertices, and to other vertices (possibly one or more of the asteroidal vertices) to create *a _{i}*-light paths. The other constructions of type B involve adding only one such vertex; we will call this vertex

*v*

_{1}.

** Construction B2:** In addition to *v*_{1}, vertices *u*_{1}and *w*_{1 }are added, such that *u*_{1} is adjacent only to *b*_{2} and *v*_{1}, and *w*_{1} is adjacent only to *b*_{3} and *v*_{1}. Then *a*_{2}−*b*_{2}−*u*_{1}−*v*_{1}−*w*_{1}−*b*_{3}−*a*_{3} is *a*_{1}-light. This construction can be applied once, in combination with constructions A1 and A2, to produce graphs 15-17. Combining B2 with A3, by adding a neighbor to *a*_{2}, does not produce a minimal graph: this combination will have a copy of the parasol, unless the vertex added to *a*_{2 }is adjacent to *v*_{1}. But, in this case, *a*_{1}, *a*_{2}, and *w*_{1} are in a strongly asteroidal triple, so *a*_{3} can be removed to make a smaller strongly asteroidal graph (it is, in fact, graph 35, which we will see later). Combining B2 and B1 (by adding *u*_{2} to the path *X*_{2}) also fails to make a minimal graph; adding any of the previous constructions to *a*_{3} or *X*_{3} will produce a graph in which *a*_{2} (at least) can be removed to make a smaller strongly asteroidal graph. Applying B2 a second time creates an irregular construction. 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 3-sun unless *v*_{1} and *v*_{2} are adjacent. Adding construction B1 to *X*_{3} will produce a sun. Adding a construction of type A to *a*_{3} creates a copy of either graph 13 or 14 (in which *u*_{1}, *u*_{2}, and *a*_{3} are a strongly asteroidal triple), unless *u*_{2} is adjacent to *v*_{1} and/or *u*_{1} is adjacent to *v*_{2}; we may assume the former. In this case, though, *v*_{2} and *w*_{2} (and the construction added to *a*_{3}) can be removed to make a smaller strongly asteroidal graph. Specifically, this is graph 18, in which, for 1 ≤ *i* ≤ 3, there is a vertex *u _{i}* adjacent only to

*b*and

_{i}*v*

_{1}. Each

*u*is

_{i}*a*-light for

_{j}*j*≠

*i*, and so for each

*i*, there is an

*a*-light path between the other two asteroidal vertices. Applying B2 a third time creates a graph which contains either a sun, or a copy of graph 18, so this does not give us an additional minimal graph.

_{i}

That wasn't so bad, was it? Things get tougher, though, with construction B3, and I may need to spend the weekend re-checking my notes before I'm ready to show you B4.

## No comments:

Post a Comment