TOPICS
Search

Graph Bandwidth


The bandwidth of a connected graph G is the minimum matrix bandwidth among all possible adjacency matrices of graphs isomorphic to G. Equivalently, it is the minimum graph dilation of a numbering of a graph. Bandwidth is variously denoted bw(G), B(G), or phi(G).

The bandwidth of the singleton graph is not defined, but the conventions bw(K_1)=0 or bw(K_1)=1 (Miller 1988) are sometimes adopted.

The bandwidth of a disconnected graph is the maximum of the bandwidths of its connected components.

The bandwidth bw(G) of a connected graph G satisfies the inequalities

 [(n-1)/(diam(G))]<=bw(G)<=n-diam(G)

(Chinn et al. 1982), where n=|G| is the vertex count of G and G is the graph diameter and

 bw(G)>=chi(G)-1,

where chi(G) 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 k-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.

Cite this as:

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

Subject classifications