The bandwidth of a connected graph is the minimum matrix bandwidth among all possible adjacency matrices of graphs isomorphic to . Equivalently, it is the minimum graph dilation of a numbering of a graph. Bandwidth is variously denoted , , or .
The bandwidth of the singleton graph is not defined, but the conventions or (Miller 1988) are sometimes adopted.
The bandwidth of a disconnected graph is the maximum of the bandwidths of its connected components.
The bandwidth of a connected graph satisfies the inequalities
(Chinn et al. 1982), where is the vertex count of and is the graph diameter and
where is the chromatic number.
Computing the bandwidth of a graph is NP-hard.
Bounds for the bandwidth of a graph have been considered by (Harper 1964), and the bandwidth of the -cube was determined by Harper (Harper 1966, Wang and Wu 2007, Harper 2010).
Special cases are summarized in the following table.