Distances in cocomparability graphs and their powers (Q1183347)

All graphs considered are finite and connected. For any nonnegative integer \(i\), let \(\Gamma_ i\) denote the class of graphs obeying some linear ordering \(v_ 1< v_ 2<\cdots<v_ n\) of its vertices such that \(d(x,y)+d(y,z)\leq d(x,z)+i\) holds for all vertices \(x<y<z\). It is easy to see that \(\Gamma_ 0\) is the set of all paths. In this paper it is shown that \(\Gamma_ 1\) is the class of proper interval graphs, and \(\Gamma_ 2\) the class of cocomparability graphs. From these characterizations there follows that all powers of proper interval graphs and of cocomparability graphs are again proper interval graphs and cocomparability graphs, respectively. Some additional results on proper powers of cocomparability graphs are also given, for instance these graphs have no induced subgraph isomorphic to \(K_{1,4}\) or \(K_{2,3}\).