Bipartite graphs and absolute difference tolerances

    Authors

    R. C. Brigham; J. R. Carrington;R. P. Vitray

    Comments

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

    Abbreviated Journal Title

    ARS Comb.

    Keywords

    COMPETITION GRAPHS; Mathematics

    Abstract

    An abdiff-tolerance competition graph, G = (V, E), is a graph for which each vertex i can be assigned a non-negative integer ti and at most \V\ subsets S-j of V can be found such that xy E E if and only if x and y lie in at least \t(x)-t(y)\ of the sets S-j. If G is not an abdiff-tolerance competition graph, it still is possible to find r > \V\ subsets of V having the above property. The integer r - \V\ is called the abdiff-tolerance competition number. This paper determines those complete bipartite graphs which are abdiff-tolerance competition graphs and finds an asymptotic value for the abdiff-tolerance competition number of K-l,K-n.

    Journal Title

    Ars Combinatoria

    Volume

    54

    Publication Date

    1-1-2000

    Document Type

    Article

    Language

    English

    First Page

    3

    Last Page

    27

    WOS Identifier

    WOS:000085703600001

    ISSN

    0381-7032

    Share

    COinS