Bandwidth of Graphs Resulting from the Edge Clique Covering Problem

Abstract

Let $n,k,b$ be integers with $1 \le k-1 \le b \le n$ and let $G_{n,k,b}$ be the graph whose vertices are the $k$-element subsets $X$ of $\{0,\dots,n\}$ with $\mathrm{max}(X)-\mathrm{min}(X) \le b$ and where two such vertices $X,Y$ are joined by an edge if $\mathrm{max}(X \cup Y) - \mathrm{min}(X \cup Y) \le b$. These graphs are generated by applying a transformation to maximal $k$-uniform hypergraphs of bandwidth $b$ that is used to reduce the (weak) edge clique covering problem to a vertex clique covering problem. The bandwidth of $G_{n,k,b}$ is thus the largest possible bandwidth of any transformed $k$-uniform hypergraph of bandwidth $b$. For $b\geq \frac{n+k-1}{2}$, the exact bandwidth of these graphs is determined. Moreover, the bandwidth is determined asymptotically for $b=o(n)$ and for $b$ growing linearly in $n$ with a factor $\beta \in (0,1]$, where for one case only bounds could be found. It is conjectured that the upper bound of this open case is the right asymptotic value.