Thursday, July 16, 2009

Lesson 6: There is NO lesson 6

We now know a few of the minimal forbidden subgraphs for the co-TT class of graphs:

  1. Chordless cycles (co-TT graphs are chordal)
  2. k-suns (co-TT graphs are, in fact, strongly chordal)
  3. The bad aster
  4. The parasol

Last time, we learned that we can find the minimal strongly asteroidal graphs by modifying the minimal asteroidal graphs to create light paths. Let a1, a2, and a3 be our asteroidal triple, and X1, X2, and X3 the paths connecting them, as described previously.

The only graphs we need concern ourselves with are graphs from the IIIn and IVn families, where n > 1 (graph IV1, recall, is the 3-sun). We will begin with graph III2, which is S3. This graph is unique, because of its rotational symmetry; any of the three asteroidal vertices could be a middle vertex (the rest of the graphs which we have to consider have only one middle vertex, and only one heavy path). This means we must create light paths for each of these vertices. There are several constructions that we can use to prevent an asteroidal vertex ai from being a middle vertex. I have grouped these constructions into three categories:

  • Category A constructions involve adding a vertex adjacent to ai. This vertex may or may not be adjacent to any neighbors of ai. In fact, adding a pendant vertex to ai is the easiest way to prevent ai from being a middle vertex, because it is no longer simplicial.
  • Category B constructions modify the ai-heavy path Xi by adding ai-light vertices. When category B constructions are added to more than one of the asteroidal vertices, we also gain the option of adding edges between the newly added vertices. This has to be done carefully; many graphs produced by these constructions are not strongly chordal.
  • Category C constructions combine the other two constructions, adding a new neighbor to ai which is adjacent to the ai-heavy vertices on Xi, and then adding vertices to Xi which are not (all) adjacent to this new neighbor. These are the most difficult constructions to find, but in at least one case, applying this construction to one asteroidal vertex prevents the entire triple from having a middle vertex.

We'll start with the category A constructions next time. They are fairly simple, so we should be able to get through all of them in one go. This will not be the case for the other two categories.

No comments: