Lesson 5: The Journey Begins

We're ready to start our search for minimal strongly asteroidal triples. There is a fairly important result which will make the search easier. In previous lessons, I've just been stating results and either linking to the relevant citation, or referring to my dissertation, but this result actually doesn't exist in print anywhere, so I need to prove it. As a result, this section will be much more technical than the first four; if you are not a trained mathematician, you may want to take proper safety precautions, or you may just want to skip to the end, where I sum everything up.

First, we need to introduce one more concept, that of the irreducible path. A path in a graph G is a sequence of distinct vertices x₁, x₂, ..., x_k, such that the vertex x_i is adjacent to the vertex x_i+1. If x_i and x_j are adjacent in G, and i and j differ by more than one, the path is reducible. For example, if a path has vertices x₁, x₂, ..., x₆, and x₂ is adjacent to x₅, then we can skip over vertices x₃ and x₄, making a shorter path between x₁ and x₆. A path which is not reducible is irreducible. Lekkerkerker and Boland showed that the paths in a minimal AT must be irreducible. Once more, let us consider the minimal asteroidal graphs, below.

Suppose that G is a chordal, strongly asteroidal graph, and that no proper subgraph of G is strongly asteroidal (in other words, G is minimal). As was mentioned in lesson 2, the bad aster and parasol (graphs I and II) are strongly asteroidal. These are also mimimally asteroidal, so these are our first two minimal strongly asteroidal graphs. In lesson 3, I stated that k-suns are also minimal strongly asteroidal graphs. Recall that a strongly chordal graph is one which is chordal and sun-free, so, as we search for the other minimal sATs, we may assume that G is strongly chordal, not just chordal.

Let a₁, a₂, and a₃ be a strongly asteroidal triple in G. Note that, even if G is minimal, it may contain more than one sAT. We may have to choose a specific triple in a few sentences, but, for now, let's just pick the first one we find.

Let W₁, W₂, and W₃ be paths such that W_i is a_i-light, and contains no neighbor of a_i. Each of these paths contains an irreducible path, if it is not itself irreducible; let W′₁, W′₂, and W′₃ be these irreducible paths.

Because G is minimal, it follows that
W₁ ∪W₂ ∪W₃ ∪ N(a₁) ∪ N(a₂) ∪ N(a₃) = G

(where N(v) refers to the open neighborhood of v - the set of all vertices adjacent to v.)
If we consider W′₁ ∪ W′₂ ∪ W′₃, each a_i must be simplicial: if a_i has two neighbors b_i and c_i (it will not have more, as each W′_i is irreducible), then the three paths contain a cycle which contains b_i−a_i−c_i as consecutive vertices, where b_i ≠ c_i and a_i has no other neighbors. Then (because G is chordal) b_i is adjacent to c_i. Further, because a_i is necessarily a_j-light for j ≠ i, there is no need to place a vertex of W_j between a_i and either b_i or c_i. Therefore, we may assume that each a_i is simplicial in W₁ ∪ W₂ ∪ W₃. Finally (and here's where we may have to pick a different triple), we may assume that each a_i has at least one neighbor adjacent to vertices on W_i: if not, then let b be any neighbor of a_i. Then, because a_i is not adjacent to any member of W_i, b is also in a sAT with the vertices a_j , j ≠ i. If b has a neighbor adjacent to a member of W_i, then replace a_i with b; if it does not, then G is not minimal.

Now, let G′ be a minimal subgraph such that a₁, a₂, and a₃ are asteroidal. In other words, remove as many vertices from G as we can while keeping those three vertices as an AT (not a sAT). Then G' is a minimal asteroidal triple - in other words, G' is one of the graphs above!

To see this, note that G′ is a subgraph of W′₁ ∪ W′₂ ∪ W′₃, and that each of the vertices a_i is necessarily simplicial in G′, and are the only simplicial vertices in G′. Let X₁, X₂, and X₃ be irreducible paths of G′ such that X_i contains no neighbor of a_i (while connecting the other two vertices in the triple). If G′ contains another minimal asteroidal triple, then at least one of a₁, a₂, or a₃ is not in this triple. Because this vertex is simplicial, it would not be part of an irreducible path; thus, it can be removed to make a smaller asteroidal graph. Without loss of generality, suppose that a₁ can be removed. Then G′−a₁ has an asteroidal triple of simplicial points (this is a result of Lekkerkerker and Boland, in the paper linked above). The only simplicial points are a₂, a₃, and (possibly) the neighbors of a₁, so a₁ has some neighbor b which is in an asteroidal triple with a₂ and a₃. Then b is the next vertex on one of the irreducible paths X₂ or X₃; without loss of generality, suppose b is on X₂. Consider W₂ and W₃; if b is not the second vertex (after a₁) of these paths, then it is adjacent to that vertex. Because b is not adjacent to every neighbor of a₂ or a₃, we can replace a₁ with b as the first vertex of W₂ and W₃, and these paths will still be a₂-light and a₃-light, respectively. If any a₂−a₃ path is b-light, then b, a₂, and a₃ are strongly asteroidal in G−a₁, which contradicts the minimality of G. So, X₁ must be b-heavy. Specifically, X₁ must have two consecutive vertices u and v (with v closer to a₂) adjacent to the next vertex on X₂; call this vertex c. None of these vertices can be a₃, so we may assume that u is not a neighbor of a₃. Neither u nor c is adjacent to a₁, so the portion of X₁ from a₂ to a, plus the portion of X₂ from c to a₃, contains no neighbor of a₁. Thus, we can eliminate v, and any vertices of X₁ between v and a₃, and obtain a proper subgraph of G′ in which a₁, a₂, and a₃ are still asteroidal, a contradiction. Phew!

This result implies that we can obtain the minimal strongly asteroidal graphs by simply appending vertices to the minimal asteroidal graphs in such a way as to make the asteroidal triples strongly asteroidal. We can break down our search for the strongly asteroidal graphs by looking at the minimal asteroidal graphs they contain. We'll get started on the first few cases next time.