Competition graph (of a tournament): различия между версиями

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

Let <math>O(x)</math> be the set of vertices that <math>x</math> beats.

Given a tournament <math>T</math> with a vertex set <math>V(T)</math>, the '''competition graph''' of <math>T</math>,

denoted <math>C(T)</math>, is the graph on <math>V(T)</math> with an edge between vertices

<math>x</math> and <math>y</math> if and only if <math>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>D</math>, the '''competition graph''' of <math>D</math> has the same set of vertices as <math>D</math> and an edge between vertices <math>u</math> and <math>v</math> if and only if there is a vertex <math>x</math> in <math>D</math> such that <math>(u,x)</math> and <math>(v,x)</math> are arcs of <math>D</math>. The '''competition number''' of a graph <math>G</math>, denoted by <math>k(G)</math>, is the smallest number <math>k</math> such that <math>G</math> with <math>k</math> isolated vertices is a competition graph of an acyclic digraph.

The '''competition-common enemy graph''' of <math>D</math> has the same set of

vertices as <math>D</math> and an edge between vertices <math>u</math> and <math>v</math> if and only if there are vertices <math>w</math> and <math>x</math> in <math>D</math> such that <math>(w,u)</math>, <math>(w,v)</math>, <math>(u,x)</math> and <math>(v,x)</math> are arcs in <math>D</math>. The '''double competition number''' of a graph <math>G</math>, denoted by

<math>dk(G)</math>, is the smallest number <math>k</math> such that <math>G</math> with <math>k</math> isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known

that <math>dk(G) \leq k(G) + 1</math> for any graph <math>G</math>.