Yesterday, I introduced (again) the strongly asteroidal triple, and began laying the groundwork for the search for minimal strongly asteroidal graphs. First, though, I should mention where the term "strongly asteroidal" comes from. The sAT is related to two weaker conditions:

Given three distinct vertices *a*, *b*, and *c* in a graph, if there are paths between each pair of vertices which contain no neighbor of the third, then *a*, *b*, and *c* are an *asteroidal triple (AT)*. If the paths between each pair of vertices do not contain two consecutive neighbors of the third, then *a*, *b*, and *c* are a *astral triple*. Every strongly asteroidal triple is also asteroidal, and every asteroidal triple is also astral. The astral and asteroidal triples are known in graph theory for being *forbidden subgraphs* of other graph classes. Interval graphs were shown by Lekkerkerker and Boland to be precisely the graphs which are chordal and *AT-free* (in other words, containing no asteroidal triple). Jackowski showed that unit interval graphs (interval graphs in which each interval is the same length) are precisely the graphs which are astral triple-free.

The three graphs to the left are the minimal chordal graphs containing an astral triple (each cycle of length at least 4 also contains astral triples). The graph on the far left is known as the *claw*, and is also denoted *K*_{1,3}. The graph on the right, the *3-sun*, is denoted *S*_{3}; the middle graph is its complement, denoted *S*_{3}.

These four graphs are the minimal chordal graphs containing an asteroidal triple. The first graph, which one of my advisors refers to as the "bad aster," is sometimes denoted *T*_{2}. The second graph has no name that I know of; I occasionally refer to it as the "parasol" (the "umbrella" is something else), or simply as Graph II. The remaining two graphs represent infinite families; the dashed line represents a path with as many vertices as desired (even 0, in which case the vertices on either end are the same vertex), all of which are adjacent to the neighbor(s) of the "top" vertex. The smallest member of family III, graph III_{2}, is *S*_{3}. In family IV, the entire path on the "bottom" may just have one vertex, so the smallest member of this family, graph IV_{1}, is the 3-sun.

A quick check of these graphs reveals that the asteroidal triples in the bad aster and the parasol are also strongly asteroidal, as is the 3-sun. However, for *n* ≥ 2, graphs III_{n} and IV_{n} do not contain a sAT, as every path between the "right" and "left" asteroidal vertices either passes through a neighbor of the "top" vertex, or contains consecutive vertices adjacent to all of those neighbors (I refer to such a path as *heavy)*. More on heavy paths and *middle vertices* later; tomorrow, I'll talk about suns and strongly chordal graphs.

## No comments:

Post a Comment