Semibandwidth of Bipartite Graphs and Matrices

Richard A. Brualdi1, Kevin F. McDougal 1
1 Department of Mathematics University of Wisconsin Madison, WI 53706 ULS.A.

Abstract

We define the semibandwidth of a bipartite graph (whose bipartition is specified), which is a bipartite analogue of the bandwidth of a graph, and develop some of its properties. The motivation for this concept comes from the question of transforming a matrix by row and column permutations to as close to triangular form as possible.