Competition graph (of a tournament)

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

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.