In the previous lesson, I broke down the categories of construction which we can use to change an asteroidal triple into a strongly asteroidal triple. Today, we'll examine the category A constructions. Right now, we're only looking at *S*_{3}; let's label the vertices of the asteroidal triple as *a*_{1}, *a*_{2}, and *a*_{3}, and let *b*_{1}, *b*_{2}, and *b*_{3} be their respective neighbors. Then the path *X*_{1}, for example, would be *a*_{2}-*b*_{2}-*b*_{3}-*a*_{3}. Each path *X _{i}* is

*a*-heavy; our goal is to add vertices in such a way as to make either make this path

_{i}*a*-light, or to create a new path that is

_{i}*a*-light.

_{i}The category A constructions involve adding a single vertex adjacent to the vertex *a _{i}*, and possibly to additional vertices, specifically to prevent

*a*from being a middle vertex. There are three constructions in this category, each of which involves adding only one vertex, which we will call

_{i}*v*.

Before we go further: when describing each construction, in this lesson and in future lessons, I will assume that vertices are being added for the explicit purpose of preventing *a*_{1} from being a middle vertex unless otherwise noted. Some constructions may affect other vertices or paths, and some constructions have special considerations when they are being used more than once; I will discuss these considerations when they come up.

**Construction A1:** *v* is a pendant vertex; in other words, the *v* is adjacent only to *a*_{1}. This means that *a*_{1} is no longer simplicial, and thus cannot be a middle vertex. This construction can be applied to all three vertices to produce a minimal sAT; this is graph 3, shown below.

**Construction A2:** *v* is adjacent to both *a*_{1} and *b*_{1}. While *a*_{1} is still simplicial, *v* is not adjacent to any vertex on the path *X*_{1}, which makes this path *a*_{1}-light. This construction can be applied to all three vertices, to produce graph 4; or, it can be applied in combination with construction A1 to produce graphs 5 and 6, shown below.

**Construction A3:** *v* is adjacent to both *a*_{1} and *b*_{1}, and to one of the other interior vertices; in the example at left, *v* is adjacent to *b*_{3}. Like construction A2, this makes the path *X*_{1} *a*_{1}-light. However, the path *a*_{1}-*v*-*b*_{3}-*a*_{3} is *a*_{2}-light, so this construction also prevents *a*_{2} from being a middle vertex! Thus, only one more construction is necessary to create a minimal sAT. If we attempt to combine this with construction A1, then we create a graph which contains the bad aster. However, combining it with construction A2 creates graph 7, below. Construction A3 can be applied twice, but the second added vertex must be adjacent to the same interior vertices (in the example above, *b*_{1} and *b*_{3}) as *v* to create a minimal sAT. The second added vertex may be adjacent to *v* or not. If it is not, we create graph 8; if it is adjacent to *v*, we create graph 9.

Other adjacencies for *v* do not create new constructions in this category. If *v* is adjacent to both *b*_{2} and *b*_{3}, then we create no new light paths, so adding *v* would not prevent any of the asteroidal vertices from being the middle vertex. If *v* is adjacent to any of the other asteroidal vertices, then this would create a new light path, but the other adjacencies required (to keep our graph strongly chordal) will actually fall under category B or C. In this vein, construction A3 might be considered a category B construction; I have placed this construction in category A because it fits the definition of adding exactly one vertex, which is adjacent to exactly one asteroidal vertex, and which prevents that asteroidal vertex from being a middle vertex.

Next time, we'll get started on the category B constructions. Because each new construction can be combined (in most cases) with previous constructions, I'll probably break this category up into two or more parts. This also means fewer breaks if I want to get through this, so maybe it will have the added benefit of speeding up the lessons.

## No comments:

Post a Comment