2015•arXiv (Cornell University)Open access

On powers of interval graphs and their orders

Florent Foucaud, Reza Naserasr, Aline Parreau, Petru Valicov

Open full text 1 citations

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.

Open-access reader

About this research paper

What this paper is about

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.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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.

Key concepts: Interval graph, Combinatorics, Mathematics, Interval (graph theory), Discrete mathematics, Graph, Unit interval, Indifference graph

Related papers

Back to paper searchBrowse research topicsOriginal source
On powers of interval graphs and their orders — Research Paper | ScholarLens