Bandwidth of graphs resulting from the edge clique covering problem

Let n, k, b be integers with 1 <= k -1 <= b <= n and let G(n,k,b) be the graph whose vertices are the k-element subsets X of {0, ..., n} with max(X) - min(X) <= b and where two such vertices X, Y are joined by an edge if max(XUY)-min(XUY) <= 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 >= 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 is an element of (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.