 TOPICS  # Graph Bandwidth

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.

 graph bandwidth antiprism graph 4 cocktail party graph  complete bipartite graph  complete graph  cycle graph 2 grid graph  hypercube graph  Möbius ladder 4 pan graph 2 path graph 1 prism graph 4 star graph  sun graph triangular grid graph  wheel graph  Bandwidth, Broadcast Time, Gossiping, Graph Dilation, Pathwidth, Treewidth

## Explore with Wolfram|Alpha More things to try:

## 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.

## Cite this as:

Weisstein, Eric W. "Graph Bandwidth." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphBandwidth.html