×

Powers of asteroidal triple-free graphs with applications. (English) Zbl 1073.05566

An ordering \(v_1,\ldots ,v_n\) of the vertices of a graph \(G\) is said to be \(k\)-cocomparability if for each two vertices \(v_{i_1}\) and \(v_{i_2}\), \(1\leq i_1<i_2\leq n\) whose distance is at most \(k\), and each vertex \(v_j\), \(i_1<j<i_2\), the distance of \(v_j\) from \(v_{i_1}\) or from \(v_{i_2}\) is at most \(k\). It can be observed that the \(k\)-th power \(G^k\) of a graph \(G\) is a cocomparability graph iff \(G\) admits a \(k\)-cocomparability ordering on its vertices. This is used by the authors to obtain the following two results: If the \(k\)-th power \(G^k\) of a graph \(G\) is a cocomparability graph, then each \(G^l\) for \(l\geq k\) is also a cocomparability graph. Every power \(G^k\), \(k\geq 2\), of an AT-free graph \(G\) is a cocomparability graph. A graph \(G\) is said to be AT-free if it does not contain an asteroidal triple (AT) as a subgraph, i.e., a subgraph containing a triple of independent vertices such that there is a path between any two of them avoiding a neighborhood of the remaining one. Several algorithmic corollaries of the latter result are also presented.

MSC:

05C75 Structural characterization of families of graphs