**Originators:** Folklore?
(presented by G. Isaak - REGS 2010)

**Definitions:**
An * oriented graph * is an orientation of a (simple) graph; the edges,
having distinct unordered pairs of two vertices, are turned into ordered pairs.
The *outdegree* of a vertex *v*, written *d ^{+}(v)* is
the number of such ordered pairs in which it appears first, and the

A *tournament* is an orientation of a complete graph, modeling
a "round-robin tournament", in which each team plays each other exactly once,
with a winner declared. From this perspective, an oriented graph models a
round-robin tournament with ties. In a FIFA round-robin tournament (World
Cup soccer), the score of a team is 3 times the number of wins plus the number
of ties. The *FIFA score* of a vertex *v* in an oriented
*n*-vertex graph is thus
*3d ^{+}(v)+(n-1-d^{+}(v)-d¯(v))*.
The

**Problem 1:**
Characterize integer lists that can occur as the FIFA score list of some
oriented graph, or show that the problem of recognizing such lists is
NP-complete.

**Comments:**
This problem has probably been asked many times. A related problem is shown to
be NP-complete in [Pal]. For ordinary *n*-vertex tournaments, Landau [L]
characterized the realizable score lists as the nondecreasing nonnegative
integer *n*-tuples *d* such that
∑* _{i=1}^{k}d_{i} ≥ k(k-1)/2*
for each

Characterizations are also known for (outdegree,indegree)-lists of digraphs
(allowing any multiplicity for each ordered pair). For a given graph *G*,
network flow can be used to determine if there is an orientation with specified
outdegrees and indegrees, and Hakimi [H] gave a necessary and sufficient
condition.

Oriented graphs correspond to tournaments with ties scored by *1,0,-1*
points for win,tie,loss, respectively; see [MWW] for essentially this
situation. When the scores give consecutive integer weights to the three
outcomes, characterizations of the realizable score lists follow from linear
programming duality. Variations of Problem 1 can be asked for any weighting of
the three outcomes.

**Problem 2:**
Find interesting sufficient conditions or special classes of FIFA lists that
can be characterized.

**Problem 3:**
Characterize (outdegree,indegree) lists for oriented graphs.
(A summer 2010 REU at Lafayette has done this when each team
has at most one tie.)

**Problem 4:**
Describe a collection of `elementary switching operations' so that any two
tournaments with the same FIFA score can be obtained from each other using
these operations.

**Comments:**
For ordinary tournaments, Ryser [R] proved that each tournament with given
vertex scores can be obtained from any other with the same vertex scores by
iteratively reversing the direction on cycles of length 3; for analogous
results involving reversal of cycles of other lengths, see [W] and [T].

**References:**

[H] S. L. Hakimi, On the degrees of the vertices of a directed graph.
{\it J. Franklin Inst.} 279 (1965), 290-308.

[L] Landau, H. G. On dominance relations and the structure of animal societies.
III. The condition for a score structure. Bull. Math. Biophys. 15, (1953).
143-148.

[MWW] Mubayi, Dhruv; Will, Todd G.; West, Douglas B.;
Realizing degree imbalances in directed graphs.
Discrete Math. 239 (2001), no. 1-3, 147-153.

[Pal] Palvolgyi, Domotor; Deciding Soccer Scores and Partial orientations of
graphs, Acta Univ. Sapientiae, Mathematica, 1 (2009) 35-42.

[R] Ryser, H. J.
Matrices of zeros and ones in combinatorial mathematics, in *Recent Advances
in Matrix Theory (Proc. Advanced Seminar, Math. Res. Center, U.S. Army, Univ.
Wisconsin, Madison, Wis., 1963)* (Univ. Wisconsin Press, Madison, Wis.,
1964) 103-124.

[T] Thomassen, Carsten; Arc reversals in tournaments. Discrete Math. 71
(1988), no. 1, 73-86.

[W] Waldrop, Clay, Jr. An ARC-reversal theorem for tournaments. Proceedings of
the Seventh Southeastern Conference on Combinatorics, Graph Theory, and
Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp. 501-507.
Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976.