Edge-bandwidth of grids and tori

Oleg Pikhurko and Jerzy Wojciechowski
Theoretical Computer Science
Volume 369, Issues 1-3 , 15 December 2006, Pages 35-43
http://dx.doi.org/10.1016/j.tcs.2006.06.018

辺バンド幅 (edge-bandwidth) に関する論文．
パス×パスというグラフ (俗にいう「格子」) の辺バンド幅を決定している．
それによると，頂点数nとmのパスの積の辺バンド幅は2min(n,m)-1となる (ただし，max(n,m)≧3のとき)．
同様に，頂点数nとmのサイクルの積のバンド幅が4n-5から4nの間にあることも示している (ただし，m≧n≧3)．