Bandwidth edge counts for linear arrangements of rectangular grids

✍ Scribed by Fishburn, Peter; Wright, Paul

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 190 KB
• Volume: 26
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199712)26:4<195::aid-jgt3>3.0.co;2-l

✦ Synopsis

Let G n,m denote a graph with nm vertices arranged in n rows and m ≥ max{n, 2} columns with an edge {u, v} between vertices u and v if they are adjacent horizontally or vertically. The bandwidth of G n,m is known to equal n. We prove that the number of edges in a bandwidth-achieving linear arrangement f from the vertex set of G n,m onto {1, 2, . . . , nm} for which |f (u) -f (v)| = n can range from 2(n -1) + n(m -n) up to n(m -1). The lower bound is attained for a down-diagonal lexicographic linear arrangement; the upper bound is attained by a column-row lexicographic linear arrangement.