Tournaments and Rankings

Tournaments

Definition: A Tournament is a directed graph $G$ so that for every pair $x, y \in V(G)$, then either $(x, y) \in E(D)$ (a directed edge from $x$ going to $y$) or $(y, x) \in E(D)$ (a directed edge from $y$ going to $x$).

By the definition above, a tournament on $n$-vertices can be thought of as an orientation of a complete graph $K_n$. For example, let's look at the following tournament on $4$ vertices:

The underlying graph is a complete graph on $4$ vertices, $K_4$, and there exists precisely one directed edge between each vertices, hence, the graph above is a tournament.

Number of Edges in Tournaments

Because a tournament is essentially just a directed complete graph, there will always be exactly $\frac{n!}{2(n - 2)!}$ arcs where n represents the number of vertices the tournament is on. For example, any tournament on $4$ vertices will have precisely $\frac{4!}{2 \cdot 2!} = 6$ edges.

Rankings

Definition: A Ranking for a tournament graph $G$ is an ordered list of vertices $v_1, v_2, ..., v_n$ of the vertex set so that each $i = 1, 2, ..., n-1$ then $(v_1, v_2) \in E(G)$.

Additionally, we can consider rankings to be directed Hamiltonian paths. Recall that a Hamiltonian path is a walk with no repeated edges or vertices that contains all vertices in the vertex set. Hence, a directed Hamiltonian path is the exact same thing with the only difference being directed edges dictating the Hamiltonian path.

In the example above, there exists a Hamiltonian path $acdb$ so the tournament in the earlier example has a ranking.