Texas A&M University, Department of
Mathematics, 216 Milner Hall, 31st of August 2005, 3:00-3:50
Groups and Dynamics Seminar
Bandwidth for grid
based graphs: techniques and results
Vladimir Lipets of Ben Gurion
University, Israel
We present several techniques for a proof of the formula for the
bandwidth value for regular grids. This formula has been obtained by
various authors earlier, but the proof here is shorter.
Also we find a ``distance-lexicographical'' enumeration which achieves
the minimal bandwidth value for cartesian products of an arbitrary
number of path graphs (sometimes called an $n$-dimensional grid). To
the best of our knowledge, this is the first result in this direction
for products of more than two graphs.