Change in additive bandwidth when an edge is added

    Authors

    R. C. Brigham; J. R. Carrington; R. P. Vitray; D. J. Williams;J. Yellen

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    ARS Comb.

    Keywords

    Mathematics

    Abstract

    Let G = (V, E) be an n-vertex graph and f : V -- > {1,2,...,n} be a bijection. The additive bandwidth of G, denoted B+(G), is given by B+ (G) = min(f) max(uvis an element ofE) \f(u) + f(v) - (n + 1)\, where the minimum ranges over all possible bijections f. The additive bandwidth cannot decrease when an edge is added, but it can increase to a value which is as much as three times the original additive bandwidth. The actual increase depends on B+ (G) and n and is completely determined.

    Journal Title

    Ars Combinatoria

    Volume

    27

    Publication Date

    1-1-2003

    Document Type

    Article

    Language

    English

    First Page

    283

    Last Page

    317

    WOS Identifier

    WOS:000180076200005

    ISSN

    0381-7032

    Share

    COinS