We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the graph; one on each side of the cut. This fixing results in several smaller subproblems that need to be solved to obtain the new bound. In order to efficiently solve these subproblems we exploit symmetry in the data; that is, both symmetry in the min-cut problem and symmetry in the graphs. Our approach results in the best known lower bounds for the bandwidth of all graphs under consideration, i.e., Hamming graphs, 3-dimensional generalized Hamming graphs, Johnson graphs, and Kneser graphs, with up to 216 vertices.
Citation
Technical report, Tilburg University, December 2012