An Upper Bound for the Depth-$r$ Interval Number of the Complete Graph

Abstract

A $t$-interval representation $f$ of a graph $G$ is a function which assigns to each vertex $v\in V(G)$ a union of at most $t$ closed intervals $I_{v,1},I_{v,2},\dots ,I_{v,t}$ on the real line such that $f(v)\cap f(w)\ne \mathrm{\varnothing }$ if and only if $v,w\in V(G)$ are adjacent. If no real number lies in more than $r$ intervals of the representation, we say the interval representation has depth $r$. The least positive integer $t$ for which there exists a $t$-representation of depth $r$ of $G$ is called the depth-$r$ interval number $i_r(G)$. E. R. Scheinerman proved that $i_2(K_n)=\lceil \frac{n}{2}\rceil$ for $n\ge 2$ and that $\lceil \frac{n-1}{2(r-1)}+\frac{r}{2n}\rceil \le i_r(K_n)\le \frac{n}{2r-2}+1+2\lceil lo{g}_{r}n\rceil$. In the following paper, we will see by construction that $i_3(K_n)=\lceil \frac{n-1}{4}+\frac{3}{2n}\rceil$. If $n\ge 5$, this is equal to $\lceil \frac{n}{4}\rceil$. The main theorem is: if $n\ge r\ge 4$, then $i_r(K_n)\le max\{\lceil \frac{n-2}{2(r-1)}+\frac{1}{2}\rceil ,2\}$. The difference between the lower and upper bounds is at most $1$.