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
![[(n-1)/(diam(G))]<=bw(G)<=n-diam(G)](/images/equations/GraphBandwidth/NumberedEquation1.svg) |
(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.
![|_1/2[max(m,n)-1]_|+min(m,n)](/images/equations/GraphBandwidth/Inline18.svg)
