Powers of Asteroidal Triple-free Graphs with Applications.
Jou–Ming Chang, Chin-Wen Ho, Ming‐Tat Ko · 2003
. An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power G k #k # 2# of an AT-free graph G is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs. Keywords: Asteroidal triple, AT-free graphs, Cocomparability graphs, Powers of graphs. 1. Introduction An asteroidal triple #AT for short# of a graph is an independent set of three vertices such that every two of them are joined by a path avoiding the closed neighborhood of the third. A g...