Asteroidal triple-free graph

In graph theory, an asteroidal triple-free graph or AT-free graph is a graph that contains no asteroidal triple.

Definition

An asteroidal triple is an independent set of three vertices ${\displaystyle {x,y,z}}$ such that each pair is joined by a path that avoids the neighborhood of the third vertex. More formally, in a graph ${\displaystyle G}$, three vertices ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ form an asteroidal triple if:

• ${\displaystyle x,y}$, and ${\displaystyle z}$ are pairwise non-adjacent
• There exists an ${\displaystyle x,y}$-path that avoids ${\displaystyle N(z)}$ (the neighborhood of ${\displaystyle z}$)
• There exists an ${\displaystyle x,z}$-path that avoids ${\displaystyle N(y)}$
• There exists a ${\displaystyle y,z}$-path that avoids ${\displaystyle N(x)}$

A graph is AT-free if it contains no asteroidal triples.

Relationship to other graph classes

AT-free graphs provide a common generalization of several important graph classes:

• Interval graphs are precisely the graphs that are both chordal and AT-free. ^[1]
• Permutation graphs are AT-free.
• Trapezoid graphs are AT-free.
• Cocomparability graphs are AT-free. ^[2]

The class hierarchy is: ${\displaystyle {\text{interval}}\subset {\text{permutation}}\subset {\text{trapezoid}}\subset {\text{cocomparability}}\subset {\text{AT-free}}}$.

Structural properties

Characterizations

AT-free graphs can be characterized in multiple ways:

• Via minimal triangulations: A graph ${\displaystyle G}$ is AT-free if and only if every minimal triangulation ${\displaystyle T(G)}$ of ${\displaystyle G}$ (i.e., every minimal chordal completion) is an interval graph. ^[3] Additionally, a claw-free AT-free graph is characterized by the property that all of its minimal chordal completions are proper interval graphs. ^[3]
• Via unrelated vertices: A graph ${\displaystyle G}$ is AT-free if and only if for every vertex ${\displaystyle x}$ of ${\displaystyle G}$, no component of the non-neighborhood of ${\displaystyle x}$ contains vertices that are unrelated with respect to ${\displaystyle x}$. ^[4]
• Via dominating pairs and the spine property. ^[4]

Dominating pairs

Every connected AT-free graph contains a dominating pair, a pair of vertices ${\displaystyle (u,v)}$ such that every path joining them is a dominating set in the graph. ^[4]

Furthermore, some dominating pair achieves the diameter of the graph. Every connected AT-free graph has a path-mccds (minimum cardinality connected dominating set that induces a path). In AT-free graphs with diameter at least 4, the vertices that can be in dominating pairs are restricted to two disjoint sets ${\displaystyle X}$ and ${\displaystyle Y}$, where ${\displaystyle (x,y)}$ is a dominating pair if and only if ${\displaystyle x\in X}$ and ${\displaystyle y\in Y}$.

Spine property

A graph ${\displaystyle G}$ is AT-free if and only if every connected induced subgraph ${\displaystyle H}$ satisfies the spine property: for every nonadjacent dominating pair ${\displaystyle (\alpha ,\beta )}$ in ${\displaystyle H}$, there exists a neighbor ${\displaystyle \alpha '}$ of ${\displaystyle \alpha }$ such that ${\displaystyle (\alpha ',\beta )}$ is a dominating pair in the component of ${\displaystyle H-{\alpha }}$ containing ${\displaystyle \beta }$. ^[4]

Decomposition

AT-free graphs admit a decomposition scheme through pokable dominating pairs. A vertex ${\displaystyle v}$ is pokable if adding a pendant vertex adjacent to ${\displaystyle v}$ preserves the AT-free property. Every connected AT-free graph contains a pokable dominating pair, and contracting certain equivalence classes of vertices (based on their domination properties) yields another AT-free graph with a pokable dominating pair. This process can be repeated until the graph is reduced to a single vertex. ^[4]

Algorithmic aspects

• Recognition: AT-free graphs can be recognized in ${\displaystyle O(n^{3})}$ time for an ${\displaystyle n}$-vertex graph. ^[4]
• Pathwidth equals treewidth: For AT-free graphs, the pathwidth equals the treewidth. ^[5]
• Perfect graphs: The strong perfect graph theorem holds for AT-free graphs, as they are a subclass of perfect graphs.

Applications

The linear structure apparent in AT-free graphs and their subclasses has led to efficient algorithms for various problems on these graphs, exploiting their dominating pair structure and other properties.

References

1. Lekkerkerker, C. G.; Boland, J. Ch. (1962), "Representation of a finite graph by a set of intervals on the real line", Fundamenta Mathematicae, 51 (1): 45–64, doi:10.4064/fm-51-1-45-64
2. Golumbic, Martin Charles; Monma, Clyde L.; Trotter, William T. Jr. (1984), "Tolerance graphs", Discrete Applied Mathematics, 9 (2): 157–170, doi:10.1016/0166-218X(84)90016-7
3. Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", 4th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Discrete Applied Mathematics , 79 (1–3): 171–188, doi: 10.1016/S0166-218X(97)00041-3 , MR   1478250
4. Corneil, Derek G.; Olariu, Stephan; Stewart, Lorna (1997), "Asteroidal Triple-Free Graphs", SIAM Journal on Discrete Mathematics, 10 (3): 399–430, doi:10.1137/S0895480193250125
5. Möhring, Rolf H. (1996), "Triangulating graphs without asteroidal triples", Discrete Applied Mathematics, 64 (3): 281–287, doi:10.1016/0166-218X(95)00095-9

See also

• Interval graph
• Chordal graph
• Chordal completion
• Cocomparability graph
• Perfect graph