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 ${\displaystyle \{x,y,z\}}$. The graph is therefore not AT-free.

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

AT-free graphs can be recognized in ${\displaystyle O(n^{3})}$ time for an ${\displaystyle n}$-vertex graph.^[4].

For AT-free graphs, the pathwidth equals the treewidth.^[5]

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.