Two-φ-tolerance competition graphs Original Research Article

Let φ be a symmetric function defined from N × N into N, where N denotes the nonnegative integers. G = (V, E) is a φ-tolerance competition graph if there is a directed graph D = (V, A) and an assignment of a nonnegative integer ti to each vertex viϵ V such that, for i ≠ j, vivj ϵ (G) if and only if ¦O(vi)∩O(Vj)¦⩾ φ (ti, tj), where O(x) = {y: xy ϵ A}. A two-φ-tolerance competition graph is a φ-tolerance competition graph in which all the ti are selected from a 2-set. Characterizations of such graphs, and relationships between them, are presented for φ equal to the minimum, maximum, and sum functions, with emphasis on the situation in which the 2-set is {0, q}.