Bipartite Graphs and Absolute Difference Tolerances

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 \in 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,n}\).