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) |
(1)
|
(Chinn et al. 1982), where 
is the vertex count of
and 
is the graph diameter and
 |
(2)
|
where 
is the chromatic number.
Every cubic graph that is also a triangle-free graph has bandwidth at least 4. This can be shown by contradiction. Suppose that
has an ordering of bandwidth at most
3, and let 
be its first vertex. The three neighbors of 
must occupy positions 2, 3, and 4. If 
is the vertex in position 2, triangle-freeness implies that
is adjacent to neither of the vertices
in positions 3 and 4. Apart from 
, the two remaining neighbors of 
must therefore both occupy position 5, which is impossible.
The wheel graph 
on 
vertices has bandwidth
 |
(3)
|
For the lower bound, placing the hub in position 
gives bandwidth at least 
. This bound is at least 3 for 
, while 
has bandwidth 3. If 
had bandwidth at most 2, its hub would occupy position 3.
The rim vertex in position 1 would then have only the rim vertex in position 2 within
distance 2, contradicting its two neighbors on the rim. For the upper bound, take
a bandwidth-2 ordering of the rim cycle graph and
insert the hub in position ![[n/2]](/images/equations/GraphBandwidth/Inline28.svg)
. Hub edges then have length at most 
, while rim edges have length at most 3.
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/Inline34.svg)
