Lesson 9: Construction B3

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

Construction B3: v₁ is adjacent to both a₂ and a₃, thus creating the path a₂-v₁-a₃, which is a₁-light. Combining this construction with previous constructions is tricky. Adding constructions A1 or A2 to both a₂ and a₃ creates a copy of the bad aster. However, if we modify these constructions by making the added vertices adjacent to v₁ as well, this creates a minimal graph (if a₂ uses the modified construction, but a₃ does not, then b₂ could be removed to make a smaller strongly asteroidal graph). Similarly, adding construction B1 to both X₂ and X₃ creates a sun, unless we modify the construction by making the added vertices adjacent to v₁. 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₁ 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₂, V₂, and W₂ are added to create the path a₁-b₁-u₂-v₂-w₂-b₃-a₃, then there is a parasol, unless v₂ and/or w₂ is adjacent to v₁. If only w₂ is adjacent to v₁, a chordless cycle is created, and if only v₂ is adjacent to v₁, a₁ and b₁ can be removed to make a smaller strongly asteroidal graph, regardless of the construction added to a₃ (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₁ and b₁ leaves a graph equivalent to combining B3 with B1 (with u₂ and v₁ standing in for a₁ and b₁). So, u₂, v₂, and w₂ must all be adjacent to v₁. Then, either a modified or unmodified type A construction can be added to a₃, producing graphs 27-30.

If construction B3 is applied twice, with vertex v₂ adjacent to a₁ and a₃ (as well as each vertex b_i), then v₁ and v₂ must be adjacent to avoid chordless cycles. Adding construction A1 or A2 to a₃ will produce a copy of graph 9, so we must add a type B construction to X₃ 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₁ and v₂. 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.