Bandwidth edge counts for linear arrange
β
Fishburn, Peter; Wright, Paul
π
Article
π
1997
π
John Wiley and Sons
π
English
β 190 KB
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 arrangeme