In graph theory, an asteroidal triple-free graph or AT-free graph is a graph that contains no asteroidal triple.
An asteroidal triple is an independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third vertex. More formally, in a graph , three vertices , , and form an asteroidal triple if:
A graph is AT-free if it contains no asteroidal triples.
AT-free graphs provide a common generalization of several important graph classes:
The class hierarchy is: .
AT-free graphs can be characterized in multiple ways:
Every connected AT-free graph contains a dominating pair, a pair of vertices 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 and , where is a dominating pair if and only if and .
A graph is AT-free if and only if every connected induced subgraph satisfies the spine property: for every nonadjacent dominating pair in , there exists a neighbor of such that is a dominating pair in the component of containing .
AT-free graphs admit a decomposition scheme through pokable dominating pairs. A vertex is pokable if adding a pendant vertex adjacent to 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.
AT-free graphs can be recognized in time for an -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.
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.