What is the size of the dominating set of the directed graph (tournament)?

Question

Algorithms

A tournament is a directed graph in which each pair of vertices {u, v} has one edge: from u to v; or from v to u.
In graph theory, the dominant set for a graph G = (V, E) is a subset D of the vertex set V such that any vertex not in D is adjacent to at least one element in D.
How can one prove that every "tournament" with the number of vertices n contains a dominating set of size log2n ?

Answer 1

Proof by induction. For one or two vertices, there will always be 1 in D.
Let degree(v) be the number of vertices incident to v.
Lemma: A tournament with n nodes will have at least one with degree() >= (n-1)/2. Otherwise, sum all degree().
On the one hand, the sum will be equal to the number of edges, i.e. n(n-1)/2. On the other hand, this sum is < n*(n-1)/2 by assumption. A contradiction, so v exists: degree(v) >= (n-1)/2
Now let's prove the main statement.
Consider a tournament with n>2 vertices. There is at least one v: degree(v) >= (n-1)/2. Let's include it in D. and delete it and everything to which it is incidental from the graph. We removed at least 1+(n-1)/2 vertices from the graph, effectively halving the number of vertices in the graph. By the induction hypothesis, there must be log(n/2) vertices in the dominating set. We added 1 to it. Therefore, in the end, we need log(n) vertices for this graph as well.
The same proof can be used to construct D - greedily include the steepest vertex in the tournament and remove it and everything dominated by it.