Tournament and cycles-reference request

Question

I am looking for any reference on the subject of tournaments (simple directed graphs with a unique oriented edge between any two vertices) and cycles. More specifically, given a function $w:E\rightarrow [0,\infty)$ such that for any vertex $v\in V$:

$$ \sum\limits_{(v,u)\in E} w\big( v,u \big)-\sum\limits_{(u,v)\in E} w\big( u,v \big)=0 $$

i.e, such that the "out-degree" and "in-degree" is according to weight function and not just the amount of edges "exiting" $v$.

---

I am wondering whether there is a "classic" result about whether conditions under which one can extend an edge to a cycle. Specifically the edge for which $w$ is maximal.

Answer 1

These sort of weighted tournaments (especially with the extra Eulerian-like condition) are not very commonly studied, but fortunately, cycles in tournaments are easy to find. I'll say what we can say in increasing order of specificity.

---

In general, for any directed graph, we can partition the vertices into strongly connected components: a vertex set $S$ is a strongly connected component when for any $v,w \in S$ there are directed paths in both directions between $v$ and $w$, and $S$ cannot be made larger and keep this property.

We can replace each strongly connected component by a single vertex to get a graph called the condensation of the original graph. This is always a directed acyclic graph. In particular, if you're looking for cycles in directed graphs, these will always be found within a single strongly connected component and never between two such components. In particular, edges that go from one strongly connected component to another can never be extended to a cycle.

However, within a strongly connected component, every edge $vw$ can be extended to a cycle, because there must be a directed path from $w$ to $v$.

---

We haven't used the condition about sums of edge weights so far. We didn't need it to find cycles, but we can use it to make some observations about strongly connected components.

I mentioned that the condensation of a directed graph is acyclic. In particular, it has a source. That source corresponds to a strongly connected component $S$ such that all edges between $S$ and the rest of the graph are oriented away from $S$.

Consider the sum $$ \sum_{v \in S} \left(\sum_{u : vu \in E} w(v,u) - \sum_{u : uv \in E} w(u,v)\right). $$ On the one hand, by the weight condition, the sum is $0$. On the other hand, every edge $uv$ with $u,v \in S$ contributes its weight twice, once with a $+$ sign and once with a $-$ sign, and so they cancel. We are left with only edges with just one endpoint in $S$, and we know all such edges are pointed away from $S$, telling us that $$ \sum_{v \in S} \sum_{u \notin S} w(v,u) = 0. $$ All weights are nonnegative, and so we conclude that all weights on the edges out of $S$ are $0$.

This means we can delete $S$ from the tournament and keep the weight condition true for all remaining vertices. By repeating this argument, we conclude that all edges between two different strongly connected components have weight $0$.

Putting this together with our previous work, we can make some conclusions:

• Every edge with positive weight can be extended to a cycle. (It's possible that some of the edges with weight $0$ can be extended as well, just not the ones that go between two strongly connected components.)
• In particular, an edge with the maximum weight can be extended to a cycle, except in the case where all edges have weight $0$ (then, weights tell us nothing).

Actually, all of the above holds for directed graphs and not just tournaments. Since we can delete all edges with weight $0$ without breaking the weight condition, we get the following statement for free:

• Each edge with positive weight can be extended to a cycle in which all edge weights are positive.

(This has algorithmic applications: to find the cycle, we can do a depth-first search that only considers edges of positive weight, which helps us because it means we're guaranteed to stay in the same strongly connected component.)