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)](https://txtdot.deep-swarm.xyz/proxy/img?url=https%3A%2F%2Fmathworld.wolfram.com%2Fimages%2Fequations%2FGraphBandwidth%2FNumberedEquation1.svg){kind=small}
(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.
See also
Bandwidth, Broadcast Time, Gossiping, Graph Dilation, Pathwidth, Treewidth
Explore with Wolfram|Alpha
References
Böttcher, J.; Preussmann, K. P.; Taraz, A.; and Würfl, A. "Bandwidth, Expansion, Treewidth, Separators and Universality for Bounded-Degree Graphs." Eur. J. Combin. 31, 1217-1227, 2010.Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; and Gibbs, N. E. "The Bandwidth Problem for Graphs and Matrices--A Survey." J. Graph Th. 6, 223-254, 1982.Chvátalová, J. "Optimal Labelling of a Product of Two Paths." Disc. Math. 11, 249-253, 1975.Harper, L. H. "Optimal Assignments of Numbers to Vertices." J. Soc. Indust. Appl. Math. 12, 131-135, 1964.Harper, L. H. "Optimal Numberings and Isoperimetric Problems on Graphs." J. Combin. Th. 1, 385-393, 1966.Harper, L. H. Global Methods for Combinatorial Isoperimetric Problems. Cambridge, England: Cambridge University Press, 2010.Miller, Z. "A Linear Algorithm for Topological Bandwidth with Degree-Three Trees." SIAM J. Comput. 17, 1018-1035, 1988.Wang, X. and Wu, X. "Recursive Structure and Bandwidth of Hales-Numbered Hypercube." 27 Aug 2007. http://arxiv.org/abs/0708.3628.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 390, 2000.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Graph Bandwidth." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphBandwidth.html