Maximum Bandwidth Under Edge Addition
Jianfang Wang, Douglas B. West, Bing Yao · Journal of Graph Theory · 1995
Abstract We determine how much the bandwidth B ( G ) of a graph G can increase when a single edge is added. Let g ( b,n ) be the maximum possible value of B ( G + e ) when G has n vertices and bandwidth b . The problem of studying when B ( G + e ) ≦ B ( G ) + 1 was originally possed by Erdos. We determine magnified image © 1996 John Wiley & Sons, Inc.