The niche graphs of interval orders

Abstract

The niche graph of a digraph $D$ is the (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if $N_D^{+}(x)\cap N_D^{+}(y)\ne \varnothing$ or $N_D^{-}(x)\cap N_D^{-}(y)\ne \varnothing$, where $N_D^{+}(x)$ (resp. $N_D^{-}(x)$) is the set of out-neighbors (resp. in-neighbors) of $x$ in $D$. A digraph $D=(V,A)$ is called a semiorder (or a unit interval order) if there exist a real-valued function $f:V\to \mathbb{R}$ on the set $V$ and a positive real number $\delta \in \mathbb{R}$ such that $(x,y)\in A$ if and only if $f(x)>f(y)+\delta$. A digraph $D=(V,A)$ is called an interval order if there exists an assignment $J$ of a closed real interval $J(x)\subset \mathbb{R}$ to each vertex $x\in V$ such that $(x,y)\in A$ if and only if $\min J(x)>\max J(y)$. S. -R. Kim and F. S. Roberts characterized the competition graphs of semiorders and interval orders in 2002, and Y. Sano characterized the competition-common enemy graphs of semiorders and interval orders in 2010. In this note, we give characterizations of the niche graphs of semiorders and interval orders.

7 pages