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].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.