Monday, July 27, 2009

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

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

If construction B3 is applied twice, with vertex v2 adjacent to a1 and a3 (as well as each vertex bi), then v1 and v2 must be adjacent to avoid chordless cycles. Adding construction A1 or A2 to a3 will produce a copy of graph 9, so we must add a type B construction to X3 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 v1 and v2. 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: