Bandwidth of Graphs Resulting from the Edge Clique Covering Problem - Engel, Konrad; Hanisch, Sebastian (The Electronic Journal of Combinatorics, 2018)
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(X Y) - min(X Y) 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-12, 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 β (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.