Maximum Bandwidth Under Edge Addition

✍ Scribed by Jianfang Wang; Douglas B. West; Bing Yao

• Book ID: 102340080
• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 191 KB
• Volume: 20
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190200109

✦ Synopsis

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.