Dominance-directed Graph

A dominance-directed graph is a directed graph such that for any distinct pair of vertices $P_i$ and $P_j$ either $P_i \rightarrow P_j$ or $P_j \rightarrow P_i$ holds, but not both. An other name for this type of the graphs is tournaments.

Example: The following graph is a dominance-directed graph.

Figure 17

Assume that $P_i \rightarrow P_j$ represent the fact that person "$P_i$ influences person $P_j$". Then the question is to find the most influential point.

Note : It can be shown that in a dominance-directed graph there is at least one vertex from which there is a 1-step or a 2-step connection to any other vertex. Therefore to determine the most influential vertices we need to compute $M + M^2$ and add the sum of entries of this matrix, the largest number is showing the most influential points.

Example

Decide whether if the following graph is a dominance-directed graph, if it is find the most powerful vertices.

Figure 15

M = $\left[ \begin{array}{rrrr} 0&1&0&1\\ 0&0&1&1\\ 1&0&0&0\\ 0&0&1&0\\ \end{array} \right]$

$M^2$ = $\left[ \begin{array}{rrrr} 0&0&2&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&0&0\\ \end{array} \right]$

$M + M^2$ = $\left[ \begin{array}{rrrr} 0&1&2&2\\ 1&0&2&1\\ 1&1&0&1\\ 1&0&1&0\\ \end{array} \right]$

Add the entries of each row to show the power the corresponding vertex.

Power of $P_1$ is 5.
Power of $P_2$ is 4.
Power of $P_3$ is 3.
Power of $P_4$ is 2.
So the vertex $P_1$ is the powerful vertex.