Competition graph (of a tournament)
Competition graph (of a tournament) --- граф конкуренции.
Let [math]\displaystyle{ O(x) }[/math] be the set of vertices that [math]\displaystyle{ x }[/math] beats. Given a tournament [math]\displaystyle{ T }[/math] with a vertex set [math]\displaystyle{ V(T) }[/math], the competition graph of [math]\displaystyle{ T }[/math], denoted [math]\displaystyle{ C(T) }[/math], is the graph on [math]\displaystyle{ V(T) }[/math] with an edge between vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] if and only if [math]\displaystyle{ O(x) \cap O(y) \neq \emptyset }[/math]. It is known that the complement of the competition graph is the domination graph.
For an arbitrary acyclic digraph [math]\displaystyle{ D }[/math], the competition graph of [math]\displaystyle{ D }[/math] has the same set of vertices as [math]\displaystyle{ D }[/math] and an edge between vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] if and only if there is a vertex [math]\displaystyle{ x }[/math] in [math]\displaystyle{ D }[/math] such that [math]\displaystyle{ (u,x) }[/math] and [math]\displaystyle{ (v,x) }[/math] are arcs of [math]\displaystyle{ D }[/math]. The competition number of a graph [math]\displaystyle{ G }[/math], denoted by [math]\displaystyle{ k(G) }[/math], is the smallest number [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ G }[/math] with [math]\displaystyle{ k }[/math] isolated vertices is a competition graph of an acyclic digraph.
The competition-common enemy graph of [math]\displaystyle{ D }[/math] has the same set of vertices as [math]\displaystyle{ D }[/math] and an edge between vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] if and only if there are vertices [math]\displaystyle{ w }[/math] and [math]\displaystyle{ x }[/math] in [math]\displaystyle{ D }[/math] such that [math]\displaystyle{ (w,u) }[/math], [math]\displaystyle{ (w,v) }[/math], [math]\displaystyle{ (u,x) }[/math] and [math]\displaystyle{ (v,x) }[/math] are arcs in [math]\displaystyle{ D }[/math]. The double competition number of a graph [math]\displaystyle{ G }[/math], denoted by [math]\displaystyle{ dk(G) }[/math], is the smallest number [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ G }[/math] with [math]\displaystyle{ k }[/math] isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known that [math]\displaystyle{ dk(G) \leq k(G) + 1 }[/math] for any graph [math]\displaystyle{ G }[/math].