Families of graphs closed under taking powers (Q5943040): Difference between revisions

In a graph \(G=(V,E)\), the distance \(d_G(x,y)\) between two vertices \(x\) and \(y\) is the minumum number of edges in any \(x\)-\(y\) path; \(d_G(x,y) = \infty\) if there is no \(x\)-\(y\) path. For a positive integer \(k\), the \(k\)th power of a graph \(G=(V,E)\), is the graph \(G^k=(V,E^k)\) whose vertex set is \(V\) and edge set \(E^k = \{xy: 1\leq d_G(x,y) \leq k\}\). Let \(A\) be the family of all interval graphs, all proper interval graphs, all cocomparability graphs or all \(m\)-trapezoidal graphs. This paper gives simple proofs for ``\(G^k \in A\) implies \(G^{k+1} \in A\)''. The first two results were originally proven by \textit{A. Raychaudhuri} [Congr. Numerantium 59, 235-242 (1987; Zbl 0642.05051)] and the third by \textit{C. Flotow} [J. Graph Theory 24, No.~4, 323-330 (1997; Zbl 0870.05041)].