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

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.