Graph bandwidth: Difference between revisions

Revision as of 20:28, 10 May 2012

Revision as of 04:10, 9 August 2012

Line 7:

==Bandwidth formulas for some graphs==

For several families of graphs , the bandwidth <math>\varphi(G)</math> is given by an explicit formula.

The bandwidth of a [[path graph]] <math>P_n</math> on n vertices is <math>1</math>, and for a complete graph <math>K_m</math> we have <math>\varphi(K_n)=n-1</math>. For the [[complete bipartite graph]] <math>K_{m,n},</math>