Graph bandwidth: Difference between revisions

Revision as of 18:10, 18 January 2015

Revision as of 18:13, 18 January 2015

Line 10:

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

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

:<math>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n</math>, assuming <math>m \ge n\ge 1</math>,

:<math>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n</math>, assuming <math>m \ge n\ge 1,</math>

which was proved by Chvátal.<ref>A remark on a problem of Harary. V. Chvátal, ''Czechoslovak Mathematical Journal'' '''20'''(1):109&ndash;111, 1970. [http://dml.cz/dmlcz/100949 http://dml.cz/dmlcz/100949]</ref> As a special case of this formula, the [[star graph]] <math>S_k = K_{k,1}</math> on ''k''&nbsp;+&nbsp;1 vertices has bandwidth <math>\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1</math>.

For the [[hypercube graph]] <math>Q_n</math> on <math>2^n</math> vertices the bandwidth was determined by {{harvtxt|Harper|1966}} to be

:<math>\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.</math>

Chvatálová showed<ref>Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' '''11''', 249&ndash;253, 1975.</ref> that the bandwidth of the <math>(''m \''&nbsp;&times ;&nbsp;''n'')</math> [[lattice graph|square grid graph]] <math>P_m \times P_n</math>, that is, the [[Cartesian product of graphs|Cartesian product]] of two path graphs on <math>m</math> and <math>n</math> vertices, is equal to <math>\&nbsp;min\{''m'',''n\''}</math>.

==Bounds==