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 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: , and are pairwise non-adjacent There exists an -path that avoids (the neighborhood of ) There exists an -path that avoids There exists a -path that avoids
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. Permutation graphs are AT-free. Trapezoid graphs are AT-free. Cocomparability graphs are AT-free.
The class hierarchy is: .
Structural properties Characterizations AT-free graphs can be characterized in multiple ways: Via minimal triangulations: A graph is AT-free if and only if every minimal triangulation of (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 is AT-free if and only if for every vertex of , no component of the non-neighborhood of contains vertices that are unrelated with respect to . Via dominating pairs and the spine property.
Dominating pairs 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 .
Spine property 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 .
Decomposition 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.
Algorithmic properties 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.
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
References