Friday, July 24, 2009

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 S3; 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 ai, 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 Xi to make it ai-light. The number of vertices we can add is limited somewhat; I'll spare the details, but an ai-light path in a minimal sAT will have a maximum of three ai-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 ai-light paths, which in turn places an upper bound on the order of the minimal graphs we can get by adding vertices to S3, 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 u1 is added, adjacent to b2 and b3. This creates an a1-light path, and thus prevents a1 from being a middle vertex. If this construction is applied twice, say by adding a vertex u2 to prevent a2 from being the middle vertex, then the new vertices cannot be adjacent: this would create a chordless cycle u1u2b1b2u1, and adding a chord between bi and ui (where i is 1 or 2) would make ui ai-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 ai-light paths. The other constructions of type B involve adding only one such vertex; we will call this vertex v1.

Construction B2: In addition to v1, vertices u1and w1 are added, such that u1 is adjacent only to b2 and v1, and w1 is adjacent only to b3 and v1. Then a2b2u1v1w1b3a3 is a1-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 a2, does not produce a minimal graph: this combination will have a copy of the parasol, unless the vertex added to a2 is adjacent to v1. But, in this case, a1, a2, and w1 are in a strongly asteroidal triple, so a3 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 u2 to the path X2) also fails to make a minimal graph; adding any of the previous constructions to a3 or X3 will produce a graph in which a2 (at least) can be removed to make a smaller strongly asteroidal graph. Applying B2 a second time creates an irregular construction. If vertices u2, v2, and w2 are added to create the path a1b1u2v2w2b3a3, then there is a 3-sun unless v1 and v2 are adjacent. Adding construction B1 to X3 will produce a sun. Adding a construction of type A to a3 creates a copy of either graph 13 or 14 (in which u1, u2, and a3 are a strongly asteroidal triple), unless u2 is adjacent to v1 and/or u1 is adjacent to v2; we may assume the former. In this case, though, v2 and w2 (and the construction added to a3) 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 ui adjacent only to bi and v1. Each ui is aj-light for ji, and so for each i, there is an ai-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.

No comments: