Tournament Kings
Tournament Kings
Definition: In a tournament graph $T$, a vertex $v \in V(T)$ is a King if and only if for every other vertex $x \in V(T)$ there exists a directed path from $v$ to $x$ with a length of at most $2$. |
If we think NON-math for a minute, we note that this definition says a king in a tournament is a vertex that can "beat" any other vertex OR "beat" another vertex that can be a vertex that it cannot "beat". Graphically, a king in a tournament is as follows:
Theorem 1: In every tournament graph $T$, there exists a vertex $v \in V(T)$ that is a king |
We will not prove this theorem, however, it is important to note this important result. Also note that in a tournament, the vertex with the greatest out-degree is the king of the tournament.