On powers of interval graphs and their orders
classification
🧮 math.CO
keywords
intervalgraphsendpointextendedgraphorderspowerrepresentation
read the original abstract
It was proved by Raychaudhuri in 1987 that if a graph power $G^{k-1}$ is an interval graph, then so is the next power $G^k$. This result was extended to $m$-trapezoid graphs by Flotow in 1995. We extend the statement for interval graphs by showing that any interval representation of $G^{k-1}$ can be extended to an interval representation of $G^k$ that induces the same left endpoint and right endpoint orders. The same holds for unit interval graphs. We also show that a similar fact does not hold for trapezoid graphs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.