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

اخر الاخبار

اخبار العتبة العباسية المقدسة

خمسون عامًا من العطاء.. نجم الأعرجي خادم الزائرين بلا انقطاع

العتبة العباسية المقدسة تواصل إقامة مجالسها العزائية لإحياء شهر المحرم

العتبة العباسية المقدسة تطلق سلسلة محاضرات قرآنية عاشورائية في بابل

في مساء اليوم الخامس من المحرّم.. المواكب الكربلائيّة تواصل فعالياتها العزائية

المزيد

الآخبار الصحية

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

الآخبار التكنلوجية

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength