pith. sign in

arxiv: 1505.03459 · v2 · pith:SR4EKKHUnew · submitted 2015-05-13 · 🧮 math.CO

On powers of interval graphs and their orders

classification 🧮 math.CO
keywords intervalgraphsendpointextendedgraphorderspowerrepresentation
0
0 comments X
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.