Content deleted Content added
m Reverted edits by 49.244.171.52 (talk) to last version by ChrisGualtieri |
m →Bandwidth formulas for some graphs: Corrected bandwidth formula for hypercubes |
||
Line 14:
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_{
Chvatálová showed<ref>Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' '''11''', 249–253, 1975.</ref> that the bandwidth of the <math>(m \times 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>\min\{m,n\}</math>.
| |||