# Competition graph (of a tournament)

Перейти к:навигация, поиск

Competition graph (of a tournament)граф конкуренции.

Let $\,O(x)$ be the set of vertices that $\,x$ beats. Given a tournament $\,T$ with a vertex set $\,V(T)$, the competition graph of $\,T$, denoted $\,C(T)$, is the graph on $\,V(T)$ with an edge between vertices $\,x$ and $\,y$ if and only if $\,O(x) \cap O(y) \neq \emptyset$. It is known that the complement of the competition graph is the domination graph.

For an arbitrary acyclic digraph $\,D$, the competition graph of $\,D$ has the same set of vertices as $\,D$ and an edge between vertices $\,u$ and $\,v$ if and only if there is a vertex $\,x$ in $\,D$ such that $\,(u,x)$ and $\,(v,x)$ are arcs of $\,D$. The competition number of a graph $\,G$, denoted by $\,k(G)$, is the smallest number $\,k$ such that $\,G$ with $\,k$ isolated vertices is a competition graph of an acyclic digraph.

The competition-common enemy graph of $\,D$ has the same set of vertices as $\,D$ and an edge between vertices $\,u$ and $\,v$ if and only if there are vertices $\,w$ and $\,x$ in $\,D$ such that $\,(w,u)$, $\,(w,v)$, $\,(u,x)$ and $\,(v,x)$ are arcs in $\,D$. The double competition number of a graph $\,G$, denoted by $\,dk(G)$, is the smallest number $\,k$ such that $\,G$ with $\,k$ isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known that $\,dk(G) \leq k(G) + 1$ for any graph $\,G$.

## Литература

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