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*_{1}, *x*_{2}, ..., *x _{k}*, such that the vertex

*x*is adjacent to the vertex

_{i}*x*. If

_{i+1}*x*and

_{i}*x*are adjacent in

_{j}*G*, and

*i*and

*j*differ by more than one, the path is

*reducible*. For example, if a path has vertices

*x*

_{1},

*x*

_{2}, ...,

*x*

_{6}, and

*x*

_{2}is adjacent to

*x*

_{5}, then we can skip over vertices

*x*

_{3}and

*x*

_{4}, making a shorter path between

*x*

_{1}and

*x*

_{6}. 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*_{1}, *a*_{2}, and *a*_{3} 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*_{1}, *W*_{2}, and *W*_{3} be paths such that *W _{i}* is

*a*-light, and contains no neighbor of

_{i}*a*. Each of these paths contains an irreducible path, if it is not itself irreducible; let

_{i}*W′*

_{1},

*W′*

_{2}, and

*W′*

_{3}be these irreducible paths.

Because G is minimal, it follows that *W*_{1} ∪*W*_{2} ∪*W*_{3} ∪ *N*(*a*_{1}) ∪ *N*(*a*_{2}) ∪ *N*(*a*_{3}) = *G*

(where *N*(*v*) refers to the *open neighborhood* of *v* - the set of all vertices adjacent to *v*.)

If we consider *W′*_{1} ∪ *W′*_{2} ∪ *W′*_{3}, each *a _{i}* must be simplicial: if

*a*has two neighbors

_{i}*b*and

_{i}*c*(it will not have more, as each

_{i}*W′*is irreducible), then the three paths contain a cycle which contains

_{i}*b*as consecutive vertices, where

_{i}−a_{i}−c_{i}*b*≠

_{i}*c*and

_{i}*a*has no other neighbors. Then (because

_{i}*G*is chordal)

*b*is adjacent to

_{i}*c*. Further, because

_{i}*a*is necessarily

_{i}*a*-light for

_{j}*j*≠

*i*, there is no need to place a vertex of

*W*between

_{j}*a*and either

_{i}*b*or

_{i}*c*. Therefore, we may assume that each

_{i}*a*is simplicial in

_{i}*W*

_{1}∪

*W*

_{2}∪

*W*

_{3}. Finally (and here's where we may have to pick a different triple), we may assume that each

*a*has at least one neighbor adjacent to vertices on

_{i}*W*: if not, then let

_{i}*b*be any neighbor of

*a*. Then, because

_{i}*a*is not adjacent to any member of

_{i}*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*, then replace

_{i}*a*with

_{i}*b*; if it does not, then

*G*is not minimal.

Now, let *G′* be a minimal subgraph such that *a*_{1}, *a*_{2}, and *a*_{3} 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′*_{1} ∪ *W′*_{2} ∪ *W′*_{3}, and that each of the vertices *a _{i}* is necessarily simplicial in

*G′*, and are the only simplicial vertices in G′. Let

*X*

_{1},

*X*

_{2}, and

*X*

_{3}be irreducible paths of

*G′*such that

*X*contains no neighbor of

_{i}*a*(while connecting the other two vertices in the triple). If

_{i}*G′*contains another minimal asteroidal triple, then at least one of

*a*

_{1},

*a*

_{2}, or

*a*

_{3}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*

_{1}can be removed. Then

*G′*−

*a*

_{1}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*

_{2},

*a*

_{3}, and (possibly) the neighbors of

*a*

_{1}, so

*a*

_{1}has some neighbor

*b*which is in an asteroidal triple with

*a*

_{2}and

*a*

_{3}. Then

*b*is the next vertex on one of the irreducible paths

*X*

_{2}or

*X*

_{3}; without loss of generality, suppose

*b*is on

*X*

_{2}. Consider

*W*

_{2}and

*W*

_{3}; if

*b*is not the second vertex (after

*a*

_{1}) of these paths, then it is adjacent to that vertex. Because

*b*is not adjacent to every neighbor of

*a*

_{2}or

*a*

_{3}, we can replace

*a*

_{1}with

*b*as the first vertex of

*W*

_{2}and

*W*

_{3}, and these paths will still be

*a*

_{2}-light and

*a*

_{3}-light, respectively. If any

*a*

_{2}−

*a*

_{3}path is

*b*-light, then

*b*,

*a*

_{2}, and

*a*

_{3}are strongly asteroidal in

*G*−

*a*

_{1}, which contradicts the minimality of

*G*. So,

*X*

_{1}must be

*b*-heavy. Specifically,

*X*

_{1}must have two consecutive vertices

*u*and

*v*(with

*v*closer to

*a*

_{2}) adjacent to the next vertex on

*X*

_{2}; call this vertex

*c*. None of these vertices can be

*a*

_{3}, so we may assume that

*u*is not a neighbor of

*a*

_{3}. Neither

*u*nor

*c*is adjacent to

*a*

_{1}, so the portion of

*X*

_{1}from

*a*

_{2}to a, plus the portion of

*X*

_{2}from

*c*to

*a*

_{3}, contains no neighbor of

*a*

_{1}. Thus, we can eliminate

*v*, and any vertices of

*X*

_{1}between

*v*and

*a*

_{3}, and obtain a proper subgraph of

*G′*in which

*a*

_{1},

*a*

_{2}, and

*a*

_{3}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.

## No comments:

Post a Comment