Generalized competition graph

Generalized competition graph --- обобщенный граф конкуренции.

A different type of generalization of competition graphs was given in 1989 by Kim, McKee, McMorris, and Roberts. They defined the [math]\displaystyle{ p }[/math]-competition graph [math]\displaystyle{ G }[/math] of a digraph [math]\displaystyle{ D }[/math] as the graph with the same vertex set as [math]\displaystyle{ D }[/math] and two vertices adjacent if and only if they compete in [math]\displaystyle{ D }[/math] for at least [math]\displaystyle{ p }[/math] distinct species.

The most recent generalization is the [math]\displaystyle{ \phi }[/math]-tolerance competition graph defined in 1995. Here [math]\displaystyle{ \phi }[/math] is a non-negative valued symmetric function whose two arguments are usually assumed (but not required) to be non-negative integers. A graph [math]\displaystyle{ G = (V,E) }[/math] is a [math]\displaystyle{ \phi }[/math]-tolerance competition graph if each vertex [math]\displaystyle{ x }[/math] can be assigned a value (tolerance) [math]\displaystyle{ t_{x} }[/math] such that there exists a collection of at most [math]\displaystyle{ |V| }[/math] subsets of [math]\displaystyle{ V }[/math] having the property that an edge [math]\displaystyle{ xy }[/math] is in [math]\displaystyle{ G }[/math] if and only if [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] lie together in at least [math]\displaystyle{ \phi(t_{x}, t_{y}) }[/math] subsets. It is known that any graph can be transformed into a [math]\displaystyle{ \phi }[/math]-tolerance competition graph by adding isolated vertices, and a minimal number of such vertices, required to accomplish this, is known as the [math]\displaystyle{ \phi }[/math]-tolerance competition number. Of course, this number is 0 if the graph is a [math]\displaystyle{ \phi }[/math]-tolerance competition graph.

A graph [math]\displaystyle{ G = (V,E) }[/math] is abdiff-tolerance competition graph if for each vertex [math]\displaystyle{ i }[/math] a non-negative integer [math]\displaystyle{ t_{i} }[/math] can be assigned and at most [math]\displaystyle{ |V| }[/math] subsets [math]\displaystyle{ S_{j} }[/math] of [math]\displaystyle{ V }[/math] can be found such that [math]\displaystyle{ xy \in E }[/math] if and only if [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] lie in at least [math]\displaystyle{ |t_{x} - t_{y}| }[/math] sets [math]\displaystyle{ S_{j} }[/math].