Lesson 8: B2, or not-B2

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₃; 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_i to make it a_i-light. The number of vertices we can add is limited somewhat; I'll spare the details, but an a_i-light path in a minimal sAT will have a maximum of three a_i-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 a_i-light paths, which in turn places an upper bound on the order of the minimal graphs we can get by adding vertices to S₃, 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₁ is added, adjacent to b₂ and b₃. This creates an a₁-light path, and thus prevents a₁ from being a middle vertex. If this construction is applied twice, say by adding a vertex u₂ to prevent a₂ from being the middle vertex, then the new vertices cannot be adjacent: this would create a chordless cycle u₁−u₂−b₁−b₂−u₁, and adding a chord between b_i and u_i (where i is 1 or 2) would make u_i a_i-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.

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₁.

Construction B2: In addition to v₁, vertices u₁and w₁ are added, such that u₁ is adjacent only to b₂ and v₁, and w₁ is adjacent only to b₃ and v₁. Then a₂−b₂−u₁−v₁−w₁−b₃−a₃ is a₁-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₂, does not produce a minimal graph: this combination will have a copy of the parasol, unless the vertex added to a₂ is adjacent to v₁. But, in this case, a₁, a₂, and w₁ are in a strongly asteroidal triple, so a₃ 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₂ to the path X₂) also fails to make a minimal graph; adding any of the previous constructions to a₃ or X₃ will produce a graph in which a₂ (at least) can be removed to make a smaller strongly asteroidal graph. Applying B2 a second time creates an irregular construction. If vertices u₂, v₂, and w₂ are added to create the path a₁−b₁−u₂−v₂−w₂−b₃−a₃, then there is a 3-sun unless v₁ and v₂ are adjacent. Adding construction B1 to X₃ will produce a sun. Adding a construction of type A to a₃ creates a copy of either graph 13 or 14 (in which u₁, u₂, and a₃ are a strongly asteroidal triple), unless u₂ is adjacent to v₁ and/or u₁ is adjacent to v₂; we may assume the former. In this case, though, v₂ and w₂ (and the construction added to a₃) 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_i and v₁. Each u_i is a_j-light for j ≠ i, and so for each i, there is an a_i-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.

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.