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

A graph with an asteroidal triple, the set of vertices $\{x,y,z\}$. The graph is therefore not AT-free.

An asteroidal triple is an independent set of three vertices $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 $G$, three vertices $x$, $y$, and $z$ form an asteroidal triple if:

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

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

Relationship to other graph classes

A cocomparability graph, which is AT-free

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.
• Permutation graphs are AT-free.
• Trapezoid graphs are AT-free.
• Cocomparability graphs are AT-free.

The class hierarchy is: $\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 $G$ is AT-free if and only if every minimal triangulation $T(G)$ of $G$ (i.e., every minimal chordal completion) is an interval graph. Additionally, a claw-free AT-free graph is characterized by the property that all of its minimal chordal completions are proper interval graphs.
• Via unrelated vertices: A graph $G$ is AT-free if and only if for every vertex $x$ of $G$, no component of the non-neighborhood of $x$ contains vertices that are unrelated with respect to $x$.
• Via dominating pairs and the spine property.

Dominating pairs

Every connected AT-free graph contains a dominating pair, a pair of vertices $(u,v)$ such that every path joining them is a dominating set in the graph.

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 $X$ and $Y$, where $(x,y)$ is a dominating pair if and only if $x\in X$ and $y\in Y$.

Spine property

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

Decomposition

AT-free graphs admit a decomposition scheme through pokable dominating pairs. A vertex $v$ is pokable if adding a pendant vertex adjacent to $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.

Algorithmic properties

AT-free graphs can be recognized in $O(n^3)$ time for an $n$-vertex graph.

For AT-free graphs, the pathwidth equals the treewidth.

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.

See also

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