Title

Bipartite Graphs And Absolute Difference Tolerances

Abstract

An abdiff-tolerance competition graph, G = (V, E), is a graph for which each vertex i can be assigned a non-negative integer t i and at most |V| subsets S j of V can be found such that xy ∈ 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 1,n.

Publication Date

1-1-2000

Publication Title

Ars Combinatoria

Volume

54

Number of Pages

3-27

Document Type

Article

Personal Identifier

scopus

Socpus ID

0346972074 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0346972074

This document is currently not available here.

Share

COinS