Graph Bandwidth
المؤلف:
Böttcher, J.; Preussmann, K. P.; Taraz, A.; and Würfl, A
المصدر:
A. "Bandwidth, Expansion, Treewidth, Separators and Universality for Bounded-Degree Graphs." Eur. J. Combin. 31
الجزء والصفحة:
...
13-4-2022
1970
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  |
![|_1/2[max(m,n)-1]_|+min(m,n)](https://mathworld.wolfram.com/images/equations/GraphBandwidth/Inline18.svg) |
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  |
![<span style=]() {3 for n<=5; |_n/2_| for n>=6" src="https://mathworld.wolfram.com/images/equations/GraphBandwidth/Inline34.svg" style="height:68px; width:186px" /> |
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
