Séminaire Lotharingien de Combinatoire 55 (2006), Article B55c

MARK SEQUENCES IN DIGRAPHS

S. Pirzada^{1} and U. Samee^{2}

1Department of Mathematics, University of Kashmir, Srinagar, India

                      Email: sdpirzada@yahoo.co.in

2Department of Applied Mathematics, AMU, Aligarh, India

Abstract. A k-digraph is an orientation of a multi-graph that is without loops and contains at most k edges between any pair of distinct vertices. We obtain necessary and sufficient conditions for a sequence of non-negative integers in non-decreasing order to be a sequence of numbers, called marks (k-scores), attached to vertices of a k-digraph. We characterize irreducible and uniquely realizable mark sequences in k-digraphs.

1. Introduction

Let D be a k-digraph with vertex set V = {v_{1}, v_{2}, …, v_{n}}, and let d^{+}(v_{i}) and d^{−}(v_{i}) denote the outdegree and indegree, respectively, of a vertex v_{i}. Define p_{v_{i}} (or p_{i}) = k(n − 1) + d^{+}(v_{i}) − d^{−}(v_{i}), as the mark of v_{i}, so that 0 ≤ p_{v_{i}} ≤ 2k(n − 1). The sequence P = [p_{i}]_{1}^{n} in non-decreasing order is called the mark sequence of D.

A k-digraph can be interpreted as the result of a competition in which the participants play each other at most k times, with an arc from u to v if and only if u defeats v. A player receives two points for each win, and one point for each tie (draw), that is the case in which the two players do not play one another or the competition between the players yields no result. With this marking system, player v obtains a total of p_{v} points.

A sequence P of non-negative integers in non-decreasing order is said to be realizable if there exists a k-digraph with mark sequence P.

Any undefined terms are found in [3,5], and one should also take into account the non-standard definitions and notations introduced in this paper.

In a k-digraph, if there are x_{1} arcs directed from vertex u to vertex v, and x_{2} arcs directed from vertex v to vertex u, with 0 ≤ x_{1}, x_{2} ≤ k and 0 ≤ x_{1} + x_{2} ≤ k, we denote this by u(x_{1} − x_{2})v.

We have one of the following six possibilities between any two vertices u and v in a 2-digraph:

2000 Mathematics Subject Classification. 05C20.

(i) exactly two arcs directed from u to v, and no arc directed from v to u; this is denoted by u(2 − 0)v;

(ii) exactly two arcs directed from v to u, and no arc directed from u to v; this is

denoted by u(0 − 2)v; (iii) exactly one arc from u to v, and exactly one arc from v to u; this is denoted by

u(1 − 1)v; (iv) exactly one arc from u to v, and no arc from v to u; this is denoted by u(1−0)v;

(v) exactly one arc from v to u, and no arc from u to v; this is denoted by u(0−1)v; (vi) no arc from u to v, and no arc from v to u; this is denoted by u(0 − 0)v.

We note that a 1-digraph is an oriented graph, and a complete 1-digraph is a tournament. A k-digraph D is said to be complete if there are exactly k arcs between any pair of vertices of D.

A k-triple in a k-digraph is an induced k-subdigraph with three vertices, and is of the form u(x_{1} − x_{2})v(y_{1} − y_{2})w(z_{1} − z_{2})u, where, for i = 1, 2, we have 0 ≤ x_{i}, y_{i}, z_{i} ≤ k and 0 ≤ ∑_{i=1}^{2} x_{i}, ∑_{i=1}^{2} y_{i}, ∑_{i=1}^{2} z_{i} ≤ k. Also, in a k-digraph a 1-triple is an induced 1-subdigraph with three vertices. A 1-triple is said to be transitive if it is of the form u(1 − 0)v(1 − 0)w(0 − 1)u, or u(1 − 0)v(0 − 1)w(0 − 0)u, or u(1 − 0)v(0 − 0)w(0 − 1)u, or u(1 − 0)v(0 − 0)w(0 − 0)u, or u(0 − 0)v(0 − 0)w(0 − 0)u, otherwise it is said to be intransitive. A k-triple is said to be transitive if it contains only transitive 1-triples, and a k-digraph is said to be transitive if every of its k-triples is transitive.

A tournament is an irreflexive, complete, asymmetric digraph. The score s_{v} of a vertex v in a tournament is the number of arcs directed away from that vertex, and the score sequence S(T) of a tournament T is formed by listing the vertex scores in non-decreasing order. The following criterion is given by Landau [4].

Theorem 1.1 ([4]). A sequence [s_{i}]_{1}^{n} of non-negative integers in non-decreasing order is the score sequence of a tournament if and only if

∑_{i=1}^{k} s_{i} ≥ \binom{k}{2}, for 1 ≤ k ≤ n,

with equality for k = n.

With the marking system, the mark p_{v} of a vertex v in a tournament is given by p_{v} = 2s_{v} + n − 1, and Landau’s conditions become

∑_{i=1}^{k} p_{i} ≥ k(n + k − 2), for 1 ≤ k ≤ n,

with equality for k = n.

An oriented graph is a digraph with no symmetric pairs of directed arcs and without self-loops. Avery [2] defined a_{v} = n − 1 + d^{+}(v) − d^{−}(v), 0 ≤ a_{v} ≤ 2n − 2, as the score of a vertex v in an oriented graph D, and A = [a_{1}, a_{2}, …, a_{n}] in non-decreasing order is the score sequence of D. The following result is due to Avery, and a constructive proof can be found in [8].

Theorem 1.2 ([2]). A sequence A = [a_{i}]_{1}^{n} of non-negative integers in non-decreasing order is the score sequence of an oriented graph if and only if

∑_{i=1}^{k} a_{i} ≥ k(k − 1), for 1 ≤ k ≤ n,

with equality for k = n.

Once again, with the marking system, the mark p_{v} of a vertex v in an oriented graph is given by p_{v} = a_{v} + n − 1, and Avery’s conditions become

∑_{i=1}^{k} p_{i} ≥ k(n + k − 2), for 1 ≤ k ≤ n,

with equality for k = n.

2. Mark sequences in digraphs

A k-digraph D is said to be complete if there are exactly k arcs between every pair of vertices of D. If in a k-digraph D there are exactly k arcs, which are parallel, between every pair of vertices of D, then D is called a k tournament. A double tournament can be treated as a tournament whose arcs have been duplicated.

The following result can be easily established, and is analogous to Theorem 2.2 of Avery [2].

Lemma 2.1. If D and D′ are two k-digraphs with the same mark sequence, then D can be transformed to D′

(i) by successively transforming 1-triples in one of the following ways:

either (a) by changing the intransitive 1-triple u(1 − 0)v(1 − 0)w(1 − 0)u to a transitive 1-triple u(0 − 0)v(0 − 0)w(0 − 0)u, which has the same mark sequence, or vice versa,

or (b) by changing an intransitive 1-triple u(1−0)v(1−0)w(0−0)u to a transitive 1-triple u(0 − 0)v(0 − 0)w(0 − 1)u, which has the same mark sequence, or vice versa.

or (ii) by changing a double u(1 − 1)v to a double u(0 − 0)v which has the same mark sequence, or vice versa.

We note here that, in a transitive tournament T, all its 1-triples are of the form u(1− 0)v(1 − 0)w(0 − 1)u, for all vertices u, v and w in T. Similarly, in a transitive oriented graph, all the 1-triples are of the form u(1−0)v(1−0)w(0−1)u, u(1−0)v(0−1)w(0−0)u, u(1−0)v(0−0)w(0−1)u, u(1−0)v(0−0)w(0−0)u, u(0−0)v(0−0)w(0−0)u. Clearly, in the transitive double tournament D, we have u(2−0)v(2−0)w(0−2)u for all vertices u, v and w in D.

Now, we have the following observation.

Theorem 2.1. Among all k-digraphs with a given mark sequence those with the fewest arcs are transitive.

Proof. Let P be a mark sequence, and let D be a realization of P that is not transitive. Then D contains an intransitive 1-triple. If it is of the form u(1 − 0)v(1 − 0)w(1 − 0)u, it can be transformed by operation (i)(a) of Lemma 2.1 to a transitive 1-triple u(0 − 0)v(0 − 0)w(0 − 0)u with the same mark sequence and three arcs fewer. If D contains an intransitive 1-triple of the form u(1 − 0)v(1 − 0)w(0 − 0)u, it can be transformed by operation (i)(b) of Lemma 2.1 to a transitive 1-triple of the form u(0−0)v(0−0)w(0−1)u with the same mark sequence and one arc fewer. If D contains both types of intransitive 1-triples, then again they can be transformed to transitive 1-triples, and certainly with lesser arcs. In case D contains a double u(1 − 1)v, it can be transformed to u(0 − 0)v by operation (ii) of Lemma 2.1 with the same mark sequence and two arcs fewer. □

The following result is the existence criteria for realizability of mark sequences in k-digraphs.

Theorem 2.2. A sequence [p_{i}]_{1}^{n} of non-negative integers in non-decreasing order is the mark sequence of a k-digraph if and only if

∑_{i=1}^{t} p_{i} ≥ kt(t − 1), for 1 ≤ t ≤ n,

with equality for t = n.

Proof. (i) Sufficiency. Let q_{i} = p_{i} − k(n − 1). Then ∑_{i=1}^{n} q_{i} = 0, and we may assume that q_{1} ≤ q_{2} ≤ ⋯ ≤ q_{r} < 0 ≤ q_{r+1} ≤ ⋯ ≤ q_{n}.

Construct a network with vertex set {s, v_{1}, v_{2}, …, v_{n}, t} of cardinality n+2 as follows.

(1) There are arcs (s, v_{i}), 1 ≤ i ≤ r from the source s to vertex v_{i}. The arc (s, v_{i}) has capacity −q_{i}, 1 ≤ i ≤ r.

(2) Arcs (v_{i}, t) from v_{i} to the sink t, r + 1 ≤ i ≤ n. The arc (v_{i}, t) has capacity −q_{i}.

(3) For each pair v_{i}, v_{j} of distinct vertices (i ≠ j), we have one arc from v_{i} to v_{j} and one arc from v_{j} to v_{i}, each with capacity k.

It is easy to check that a k-digraph with mark sequence [p_{i}]_{i}^{n} can be obtained from an integral flow of value − ∑_{i=1}^{r} q_{i} = ∑_{i=r+1}^{n} q_{i} by reducing the flow on cycles of length 2 until one of the two edges has flow value zero.

In view of the max-flow-min-cut-Theorem, it suffices to check that each cut has capacity at least ∑_{i=r+1}^{n} q_{i}.

We thus assume that {s} ∪ C is a cut, C ⊆ {v_{1}, v_{2}, …, v_{n}}, |C| = t, and that |C ∩ {v_{1}, v_{2}, …, v_{r}}| = a and |C ∩ {v_{r+1}, v_{r+2}, …, v_{n}}| = b = t − a.

For its capacity, we have the following estimate.

cap({s} ∪ C) = ∑_{i:i≤r,v_{i}∉C} −q_{i} + ∑_{i:i>r,v_{i}∈C} q_{i} + t(n − t) · k

≥ − ∑_{i=a+1}^{r} q_{i} + ∑_{i=r+1}^{r+b} q_{i} + t(n − t) · k.

This expression is bounded from below by − ∑_{i=1}^{r} q_{i} = ∑_{i=r+1}^{n} q_{i} if and only if

∑_{i=1}^{a} q_{i} + ∑_{i=r+1}^{r+b} q_{i} + t(n − t) · k ≥ 0,

if and only if

∑_{i=1}^{a} p_{i} + ∑_{i=r+1}^{r+b} p_{i} + t(n − t) · k ≥ t · k(n − 1)

(since p_{i} = k(n − 1) + q_{i}), if and only if

∑_{i=1}^{a} p_{i} + ∑_{i=r+1}^{r+b} p_{i} ≥ kt(t − 1).

This latter inequality is certainly implied by the inequality

∑_{i=1}^{t} p_{i} ≥ kt(t − 1),

since the p_{i} are non-decreasing.

(ii) Necessity. Follows from the construction in (i) if we use the cuts {s} ∪ {v_{1}, v_{2}, …, v_{t}}, 1 ≤ t ≤ n. □

The following result is the existence criteria for realizability of mark sequences in 2-digraphs. The proof follows from Theorem 2.2. Here we give a different proof.

Theorem 2.3. A sequence [p_{i}]_{1}^{n} of non-negative integers in non-decreasing order is the mark sequence of a 2-digraph if and only if

∑_{i=1}^{k} p_{i} ≥ 2k(k − 1),  for 1 ≤ k ≤ n,  (2.3.1)

with equality for k = n.

Proof. Necessity. Let D be a 2-digraph with mark sequence [p_{i}]_{1}^{n}. Let W be the 2-subdigraph induced by any set of k vertices w_{1}, w_{2}, …, w_{k} of D. Let α denote the number of arcs of D that start in W and end outside W, and let β denote the number of arcs of D that start outside of W and end in W. Note that each vertex w in W, and for every vertex v of D not in W, there are at most two arcs from v to w, so that β ≤ 2k(n − k). Therefore, we have β ≤ 2nk − 2k^{2}. Then,

∑_{i=1}^{k} p_{w_{i}} = ∑_{i=1}^{k}(2n − 2 + d_{D}^{+}(w_{i}) − d_{D}^{−}(w_{i}))

= 2nk − 2k + ∑_{i=1}^{k} d_{D}^{+}(w_{i}) − ∑_{i=1}^{k} d_{D}^{−}(w_{i})

= 2nk − 2k + [∑_{i=1}^{k} d_{W}^{+} (w_{i}) + α] − [∑_{i=1}^{k} d_{W}^{−} (w_{i}) + β]

= 2nk − 2k + (number of arcs of W) + α − (number of arcs of W) − β

= 2nk − 2k + α − β  (2.3.2)

≥ 2nk − 2k − β

≥ 2nk − 2k − 2nk + 2k^{2} = 2k(k − 1).

Applying this result to the k vertices with marks p_{1}, p_{2}, …, p_{k} yields the desired inequality. If k = n, then α = β = 0, and the required equality follows from Equation (2.3.2).

Sufficiency. This is proved by contradiction. Assume all sequences of non-negative integers in non-decreasing order of length fewer than n satisfying conditions (2.3.1) be the mark sequences. Let n be the smallest and with this choice of n, p_{1} be the smallest possible such that P = [p_{i}]_{1}^{n} is not a mark sequence. Two cases arise,

(a) equality in (2.3.1) holds for some k < n, and

(b) each inequality in (2.3.1) is strict for all k < n.

Case (a). Assume k (k < n) is the smallest such that

∑_{i=1}^{k} p_{i} = 2k(k − 1).

Clearly, the sequence [p_{1}, p_{2}, …, p_{k}] satisfies conditions (2.3.1), and is a sequence with length less than n. So, by assumption, [p_{i}]_{1}^{k} is a mark sequence of some 2-digraph, say D_{1}. Further,

∑_{i=1}^{m}(p_{k+i} − 4k) = ∑_{i=1}^{m+k} p_{i} − ∑_{i=1}^{k} a_{i} − 4mk
≥ 2(m + k)(m + k − 1) − 2k(k − 1) − 4mk
= 2m(m − 1),

for each m, 1 ≤ m ≤ n − k, with equality when m = k. As m < n, thus by the minimality of n, the sequence [p_{k+1} − 4k, p_{k+2} − 4k, …, p_{n} − 4k] is the mark sequence of some 2-digraph D_{2}. The 2-digraph D of order n consisting of disjoint copies of D_{1} and D_{2}, such that u(2 − 0)v for each vertex u ∈ D_{2} and for each vertex v ∈ D_{1}, has mark sequence P = [p_{i}]_{1}^{n}, which is a contradiction.

Case (b). Assume that each inequality in condition (2.3.1) is strict for all k < n. Obviously, p_{1} > 0. Consider the sequence P′ = [p′_{i}]_{1}^{n}, defined by

p′_{i} = \begin{cases}p_{i} − 1, & if i = 1, \\ p_{i} + 1, & if i = n, \\ p_{i}, & otherwise. \end{cases}

Then,

∑_{i=1}^{k} p′_{i} = (∑_{i=1}^{k} p_{i}) − 1 > 2k(k − 1) − 1 ≥ 2k(k − 1),

for all k, 1 ≤ k < n, and

∑_{i=1}^{n} p′_{i} = (∑_{i=1}^{n} p_{i}) − 1 + 1 = 2n(n − 1).

This shows that the sequence P′ = [p′_{i}]_{1}^{n} satisfies condition (2.3.1), and therefore is a mark sequence of some 2-digraph D. Let u and v denote the vertices with marks p′_{i} = p_{i} − 1 and p′_{n} = p_{n} − 1 respectively.

If in D, u(0 − 2)v, or u(1 − 1)v, or u(1 − 0)v, or u(0 − 1)v, or u(0 − 0)v, then transforming them respectively to u(0 − 1)v, or u(1 − 0)v, or u(2 − 0)v, or u(1 − 1)v, or u(1 − 0)v, we obtain a 2-digraph with mark sequence P, a contradiction.

In D, let u(2 − 0)v. We have p′_{v} ≥ p′_{u} + 2. If there exists at least one vertex w ∈ D − {u, v} such that the 2-triples formed by the vertices u, v and w contain an intransitive 1-triple of the form u(1 − 0)v(1 − 0)w(1 − 0)u, or u(1 − 0)v(1 − 0)w(0 − 0)u, or u(1 − 0)v(0 − 0)w(1 − 0)u, transforming them respectively to u(1 − 0)v(0 − 0)w(0 − 0)u, or u(1 − 0)v(0 − 0)w(0 − 1)u, or u(1 − 0)v(0 − 1)w(0 − 0)u, we obtain a 2-digraph with mark sequence P, which is a contradiction.

Assume for each vertex w ∈ D − {u, v}, the 2-triples formed by the vertices u, v and w contain only transitive 1-triples of the form

(i) u(1 − 0)v(1 − 0)w(0 − 1)u, (ii) u(1 − 0)v(0 − 1)w(1 − 0)u, (iii) u(1 − 0)v(0 − 1)w(0 − 1)u, (iv) u(1 − 0)v(0 − 0)w(0 − 1)u,

(v) u(1 − 0)v(0 − 1)w(0 − 0)u, (vi) u(1 − 0)v(0 − 0)w(0 − 0)u. Then, clearly p′_{v} < p′_{u} + 2, since d_{u}^{+} > d_{v}^{+} and d_{u}^{−} < d_{v}^{−}, and we get a contradiction. If (i) appears for every vertex w ∈ D − {u, v}, so that the 2-triples formed by u, v

and w is of the form u(2 − 0)v(2 − 0)w(0 − 1)u, then

p′_{v} = 2n − 2 + d_{v}^{+} − d_{v}^{−} = 2n − 2 + 2(n − 2) − 2 = 4n − 8,

and

p′_{u} = 2n − 2 + d_{u}^{+} − d_{u}^{−} = 2n − 2 + n − 2 + 2 = 3n − 2.

Therefore, p′_{v} = p′_{u} + n − 6.

For n < 8, clearly p′_{v} ≤ p′_{u} + 1, a contradiction.

For n ≥ 8, we do have p′_{v} ≥ p′_{u} + 2, but then u(2 − 0)v(2 − 0)w(0 − 1)u can be transformed to u(2 − 0)v(1 − 0)w(0 − 2)u, and we get a 2-digraph with mark sequence P, a contradiction.

If (ii) appears for every vertex w ∈ D − {u, v} such that the 2-triple formed by u, v and w is of the form u(2 − 0)v(0 − 1)w(2 − 0)u, then

p′_{v} = 2n − 2 + d_{v}^{+} − d_{v}^{−} = 2n − 2 − (n − 2) − 2 = n − 2,

and

p′_{u} = 2n − 2 + d_{u}^{+} − d_{u}^{−} = 2n − 2 − 2(n − 2) = 4.

Therefore, p′_{v} − p′_{u} = n − 6, so that p′_{v} = p′_{u} + n − 6.

For n < 8, clearly p′_{v} ≤ p′_{u} + 1, a contradiction.

For n ≥ 8, we have p′_{v} ≥ p′_{u} + 2. Then, transforming u(2 − 0)v(0 − 1)w(2 − 0)u to u(2 − 0)v(0 − 2)w(1 − 0)u, we obtain a 2-digraph with mark sequence P, again a contradiction. □

Some stronger inequalities on marks in 2-digraphs can be found in [7]. The next result is the analogue of Havel–Hakimi theorem on degree sequences of simple graphs.

Theorem 2.4. Let P = [p_{i}]_{1}^{n} be a sequence of non-negative integers in non-decreasing order, where for each i, 0 ≤ p_{i} ≤ 2k(n − 1). Let P′ be obtained from P by deleting the greatest entry p_{n} (= 2k(n − 1) − r, say) and (a) if r ≤ n − 1, reducing the r greatest remaining entries by one each, or (b) if r > n − 1, reducing the r − (n − 1) greatest remaining entries by two each, and the 2n − 2 − r remaining entries by one. Then, P is a mark sequence of some k-digraph if and only if P′ (arranged in non-decreasing order) is a mark sequence of some k-digraph.

Proof. Let P′ be a mark sequence of some k-digraph D′. If P′ is obtained from P as in (a), then a k-digraph D with mark sequence P is obtained by adding a vertex v in D′ such that v((k − 1) − 0)v_{i} for those vertices v_{i} in D′ with mark v_{i} = p_{i} − 1, and v(k − 0)v_{i} for those vertices v_{i} in D′ with mark v_{i} = p_{i}. If P′ is obtained from P as in (b), then again a k-digraph D with mark sequence P is obtained by adding a vertex v in D′ such that v((k − 1) − 1)v_{i} for those vertices v_{i} in D′ with mark v_{i} = p_{i} − 2 and v((k − 1) − 0)v_{i} for those vertices v_{i} in D′ with mark v_{i} = p_{i} − 1.

Conversely, let P be the mark sequence of some k-digraph D. We assume D is transitive, if not D becomes transitive by using Lemma 2.1. Let V = {v_{1}, v_{2}, …, v_{n}} be the vertex set of D, and let p_{n} = 2k(n − 1) − r. If r ≤ n − 1, construct D such that v_{n}((k − 1) − 0)v_{i} for all i, n − r ≤ i ≤ n − 1, and v_{n}(k − 0)v_{j} for all j, 1 ≤ j ≤ n − r − 1. Clearly, D − v_{n} realizes P′ (arranged in non-decreasing order). If r > n − 1, construct D such that v_{n}((k − 1) − 1)v_{i} for all i, 2n − r − 1 ≤ i ≤ n − 1, and v_{n}((k − 1) − 0)v_{j} for all j, 1 ≤ j ≤ 2n − r − 2. Then again, D − v_{n} realizes P′ (arranged in non-decreasing order). □

Theorem 2.4 provides an algorithm for determining whether a given non-decreasing sequence P of non-negative integers is a mark sequence, and for constructing a corresponding k-digraph. At each stage, we form P′ according to Theorem 2.4 such that P′ is in non-decreasing order. If p_{n} = 2k(n − 1) − r, deleting p_{n}, and performing (a) or (b) of Theorem 2.4 according as r ≤ n − 1, or r > n − 1, we get P′ = [p′_{1}, p′_{2}, …, p′_{n−1}]. If the mark of vertex v_{i} was decreased by one in this process, then the construction yielded v_{n}((k − 1) − 0)v_{i}, and if it was decreased by two, then the construction yielded v_{n}((k − 1) − 1)v_{i}. For a vertex v_{j} whose mark remained unchanged, the construction yielded v_{n}(k − 0)v_{j}. If this procedure is applied recursively, then it tests whether or not P is a mark sequence, and if P is a mark sequence, then a k-digraph with mark sequence P is constructed.

Theorem 2.5. Let P = [p_{i}]_{1}^{n} be a sequence of non-negative integers in non-decreasing order, where for each i, 0 ≤ p_{i} ≤ 2k(n − 1). Let P′ be obtained from P by deleting the greatest entry p_{n} (= 2k(n − 1) − r, say) and (a) if r is even, say r = 2t, reducing t of the next greatest entries by two, or (b) if r is odd, say r = 2t + 1, reducing t greatest remaining entries by two, and reducing the greatest among the remaining entries by one. Then P is a mark sequence if and only if P′ (arranged in non-decreasing order) is a mark sequence.

The proof follows by using the arguments as in Theorem 2.4.

Theorem 2.5 also provides an algorithm of checking whether or not a given nondecreasing sequence P of non-negative integers is a mark sequence and for constructing a corresponding k-digraph. At each stage, we form P′ according to Theorem 2.5 such that P′ is in non-decreasing order. If p_{n} = 2k(n − 1) − r, deleting p_{n}, and performing (a), or (b), of Theorem 2.5 according as r is even or odd, we get P′ = [p′_{1}, p′_{2}, …, p′_{n−1}]. If the mark of the vertex v_{i} was decreased by two in the process, then the construction yielded v_{n}((k − 1) − 1)v_{i}, and if it was decreased by one, then the construction yielded v_{n}((k − 1) − 0)v_{i}. For a vertex v_{j} whose mark remained unchanged, the construction yielded v_{n}(k − 0)v_{j}. If this procedure is applied recursively, then it tests whether or not P is a mark sequence, and if P is a mark sequence, then a k-digraph with mark sequence P is constructed.

3. Irreducible mark sequences

A k-digraph is reducible if it is possible to partition its vertices into two nonempty sets V_{1} and V_{2} in such a way that there are exactly two arcs directed from every vertex of V_{2} to each vertex of V_{1}, and there is no arc from any vertex of V_{1} to any vertex of V_{2}. If D_{1} and D_{2} are k-digraphs having vertex sets V_{1} and V_{2} respectively, then the k-digraph D consisting of all the arcs of D_{1}, and all the arcs of D_{2}, and exactly k arcs directed from every vertex of D_{2} to each vertex of D_{1} is denoted by D = [D_{1}, D_{2}]. If this is not possible, the k-digraph is said to be irreducible. Let D_{1}, D_{2}, …, D_{h} be irreducible k-digraphs with disjoint vertex sets. Then D = [D_{1}, D_{2}, …, D_{h}] is the kdigraph having all arcs of D_{i}, 1 ≤ i ≤ h, and exactly k arcs from every vertex of D_{j} to each vertex of D_{i}, 1 ≤ i < j ≤ h. We call D_{1}, D_{2}, …, D_{h} the irreducible components of D, and such a decomposition is called the irreducible decomposition of D. A mark sequence P is said to be irreducible if all the k-digraphs D with mark sequence P are irreducible.

The following result characterizes irreducible k-digraphs.

Theorem 3.1. If D is a connected k-digraph with mark sequence P = [p_{i}]_{1}^{n}, then D is irreducible if and only if, for t = 1, 2, …, n − 1,

∑_{i=1}^{t} p_{i} > kt(t − 1)  (3.1.1)

and

∑_{i=1}^{n} p_{i} = kn(n − 1).  (3.1.2)

Proof. Let D be a connected, irreducible k-digraph having mark sequence P = [p_{i}]_{1}^{n}. Condition (3.1.2) holds, since Theorem 2.2 has already established it for any k-digraph. Condition (3.1.2) also implies that for any integer t < n, the k-subdigraph D′ induced by any set of t vertices has a sum of marks in D′ equal to kt(t−1). Since D is irreducible, therefore either there is an arc from at least one of these t vertices to at least one of the other n − t vertices, or there is exactly one arc from at least one of the other n − t vertices to at least one vertex in D′. Therefore, for 1 ≤ t < n − 1,

∑_{i=1}^{t} p_{i} ≥ kt(t − 1) + 1 > kt(t − 1).

For the converse, suppose that conditions (3.1.1) and (3.1.2) hold. It follows from Theorem 2.2 that there exists a k-digraph with mark sequence P = [p_{i}]_{1}^{n}. Assume such a k-digraph is reducible, and let D = [D_{1}, D_{2}, …, D_{h}] be the irreducible component decomposition of D. Since there are exactly k arcs from every vertex of D_{j} to each vertex of D_{i}, 1 ≤ i < j ≤ h, D is evidently connected. If m is the number of vertices in D_{1}, then m < n, and ∑_{i=1}^{m} p_{i} = km(m − 1), which is a contradiction to the given hypothesis. Hence, D is irreducible. □

We note that a disconnected k-digraph is always irreducible, since if D_{1} and D_{2} are the components of D, then there are no arcs between vertices of D_{1} and vertices of D_{2}.

The following result can be easily established.

Theorem 3.2. If D is a k-digraph with mark sequence P = [p_{i}]_{1}^{n}, and ∑_{i=1}^{r} p_{i} = kr(r − 1), ∑_{i=1}^{t} p_{i} = kt(t − 1), and ∑_{i=1}^{q} p_{i} > kq(q − 1), for r + 1 ≤ q ≤ t − 1, 0 ≤ r < t ≤ n, then the k-subdigraph induced by the vertices v_{r+1}, v_{r+2}, …, v_{t} is an irreducible component of D with mark sequence [p_{i} − kr]_{r+1}^{t}.

The mark sequence P is irreducible if D is irreducible, and the irreducible components of P are the mark sequences of the irreducible components of D. That is, if D = [D_{1}, D_{2}, …, D_{h}] is the irreducible component decomposition of a k-digraph D with mark sequence P, then the irreducible components P_{i} of P are the mark sequences of the k-subdigraphs induced by the vertices of D_{i}, 1 ≤ i ≤ h. Theorem 3.2 shows that the irreducible components of P are determined by the successive values of k for which

∑_{i=1}^{t} p_{i} = kt(t − 1),  1 ≤ t ≤ n.  (3.2.1)

This is illustrated by the following examples of 2-digraphs.

(i) Let P = [1, 3, 9, 12, 15, 20]. Equation (3.2.1) is satisfied for k = 2, 5, 6. Therefore, the irreducible components of P are [0], [1, 4, 7], [0] in ascending order.

(ii) Let P = [0, 5, 8, 11, 17, 19]. Here Equation (3.2.1) is satisfied for k = 1, 4, 6. Therefore, the irreducible components of P are [0], [1, 4, 7] and [1, 3] in ascending order.

A mark sequence is uniquely realizable if it belongs to exactly one k-digraph. The characterization of uniquely realizable score sequences in tournaments is given by Avery [1], and that of oriented graphs by S.Pirzada [6]. Now, as an observation, we have the following result.

Theorem 3.3. The mark sequence P of a k-digraph D is uniquely realizable if and only if every irreducible component of P is uniquely realizable.

The next result determines which irreducible mark sequences in 2-digraphs are uniquely realizable.

Theorem 3.4. The only irreducible mark sequences in 2-digraphs that are uniquely realizable are [0] and [1, 3].

Proof. Let P be an irreducible mark sequence, and let D with vertex set V be a 2digraph having mark sequence P. Then D is irreducible. Therefore, D cannot be partitioned into 2-subdigraphs D_{1}, D_{2}, …, D_{k} such that there are exactly two arcs from every vertex of D_{α} to each vertex of D_{β}, 1 ≤ β < α ≤ k. First assume D has n ≥ 3 vertices. Let W = {w_{1}, w_{2}, …, w_{r}} and U = {u_{1}, u_{2}, …, u_{s}} respectively be any two disjoint subsets of V such that r + s = n. Since D is irreducible, (1) there do not exist exactly two arcs from every w_{i} (1 ≤ i ≤ r) to each u_{j} (1 ≤ j ≤ s), and (2) there do not exist exactly two arcs from every u_{j} (1 ≤ j ≤ s) to each w_{i} (1 ≤ i ≤ s). First of all we consider Case (1), and then Case (2) follows by using the same argument as in (1).

Case (1). There exists at least one vertex, say w_{1}, in W, and at least one vertex, say u_{1}, in U such that either (a) w_{1}(1 − 1)u, or (b) w_{1}(0 − 2)u_{1}, or (c) w_{1}(1 − 0)u_{1}, or (d) w_{1}(0 − 1)u_{1}, or (e) w_{1}(0 − 0)u_{1}.

Assume w_{i}(2 − 0)u_{j} for each i (1 ≤ i ≤ r) and j (1 ≤ j ≤ s), except for i = j = 1.

If in D, either (a) w_{1}(1−1)u_{1}, or (e) w_{1}(0−0)u_{1}, then transforming them respectively to w_{1}(0 − 0)u_{1}, or w_{1}(1 − 1)u_{1}, gives a 2-digraph D′ with the same mark sequence. In both cases, D and D′ have different number of arcs, and thus are non-isomorphic.

(b) Let w_{1}(0−2)u_{1}. Since there are only six possibilities between w_{1} and w_{i}, therefore, for any other vertex w_{i} in W we have one of the following cases:

(i) w_{1}(2−0)w_{i}(2−0)u_{1}(2−0)w_{1}, (ii) w_{1}(1−1)w_{i}(2−0)u_{1}(2−0)w_{1}, (iii) w_{1}(1−0)w_{i}(2− 0)u_{1}(2 − 0)w_{1}, (iv) w_{1}(0 − 1)w_{i}(2 − 0)u_{1}(2 − 0)w_{1}, (v) w_{1}(0 − 0)w_{i}(2 − 0)u_{1}(2 − 0)w_{1}, (vi) w_{1}(0 − 2)w_{i}(2 − 0)u_{1}(2 − 0)w_{1}.

Transforming (i)–(v) respectively to w_{1}(1 − 0)w_{i}(1 − 0)u_{1}(1 − 0)w_{1}, w_{1}(0 − 1)w_{i}(1 − 0)u_{1}(1 − 0)w_{1}, w_{1}(0 − 0)w_{i}(1 − 0)u_{1}(1 − 0)w_{1}, w_{1}(0 − 2)w_{i}(1 − 0)u_{1}(1 − 0)w_{1}, w_{1}(0 − 1)w_{i}(1 − 0)u_{1}(1 − 0)w_{1}, gives a 2-digraph with the same mark sequence. In all these five cases, D and D′ have different number of arcs, and thus are non-isomorphic.

If (vi) occurs in D, and also w_{q}(2 − 0)w_{i} for 1 ≤ i < q ≤ r, then the 2-digraph D is reducible with irreducible components D_{1}, D_{2}, …, D_{r} respectively having vertex sets V_{1} = {u_{1}, u_{2}, …, u_{s}, w_{1}}, V_{2} = {w_{2}}, V_{3} = {w_{3}}, …, V_{k} = {w_{r}}.

Also for any vertex u_{j} in U, since there are only six possibilities between u_{1} and u_{j}, we have one of the following cases:

(vii) w_{1}(0 − 2)u_{1}(0 − 2)u_{j}(0 − 2)w_{1}, (viii) w_{1}(0 − 2)u_{1}(1 − 1)u_{j}(0 − 2)w_{1}, (ix) w_{1}(0 − 2)u_{1}(1−0)u_{j}(0−2)w_{1}, (x) w_{1}(0−2)u_{1}(0−1)u_{j}(0−2)w_{1}, (xi) w_{1}(0−2)u_{1}(0−0)u_{j}(0−2)w_{1}, (xii) w_{1}(0 − 2)u_{1}(2 − 0)u_{j}(0 − 2)w_{1}.

If any one of (vii)–(xi) appears in D, then making respectively the transformations w_{1}(0−1)u_{1}(0−1)u_{j}(0−1)w_{1}, w_{1}(0−1)u_{1}(1−0)u_{j}(0−1)w_{1}, w_{1}(0−1)u_{1}(2−0)u_{j}(0−1)w_{1}, w_{1}(0 − 1)u_{1}(1 − 1)u_{j}(0 − 1)w_{1}, w_{1}(0 − 1)u_{1}(1 − 0)u_{j}(0 − 1)w_{1}, we get a 2-digraph with the same mark sequence, but the numbers of arcs in D and D′ are different, and thus D and D′ are non-isomorphic.

If (xii) and any of (i)–(v) appear simultaneously, then there exists a 2-digraph D′ with the same mark sequence, but D and D′ have different numbers of arcs. Thus, D and D′ are non-isomorphic.

If (vi) and (xii) appear simultaneously, and also w_{q}(2 − 0)w_{i} for all 1 ≤ i < q ≤ r, then D is reducible with the irreducible components D_{1}, D_{2}, …, D_{r} having vertex sets V_{1} = {u_{1}, u_{2}, …, u_{s}, w_{1}}, V_{2} = {w_{2}}, V_{3} = {w_{3}}, …, V_{r} = {w_{r}} respectively.

(c) Let w_{1}(1 − 0)u_{1}. For any vertex w_{i} in W, since there are only six possibilities between w_{1} and w_{i}, we have one of the following cases:

(i) w_{1}(2−0)w_{i}(2−0)u_{1}(0−1)w_{1}, (ii) w_{1}(1−1)w_{i}(2−0)u_{1}(0−1)w_{1}, (iii) w_{1}(1−0)w_{i}(2− 0)u_{1}(0 − 1)w_{1}, (iv) w_{1}(0 − 1)w_{i}(2 − 0)u_{1}(0 − 1)w_{1}, (v) w_{1}(0 − 0)w_{i}(2 − 0)u_{1}(0 − 1)w_{1}, (vi) w_{1}(0 − 2)w_{i}(2 − 0)u_{1}(0 − 1)w_{1}.

For (i)–(v) making respectively the transformations w_{1}(1 − 0)w_{i}(1 − 0)u_{1}(0 − 2)w_{1}, w_{1}(0−1)w_{i}(1−0)u_{1}(0−2)w_{1}, w_{1}(0−1)w_{i}(1−0)u_{1}(0−2)w_{1}, w_{1}(1−1)w_{i}(1−0)u_{1}(2−0)w_{1}, w_{1}(0 − 1)w_{i}(1 − 0)u_{1}(2 − 1)w_{1}, we obtain a 2-digraph D′ with the same mark sequence, but the numbers of arcs in D and D′ are not equal. Thus, D and D′ are non-isomorphic.

Now, for any other vertex u_{j} in U, there are only six possibilities between u_{1} and u_{j}, and we have one of the following cases:

(vii) w_{1}(1 − 0)u_{1}(0 − 2)u_{j}(0 − 2)w_{1}, (viii) w_{1}(1 − 0)u_{1}(1 − 1)u_{j}(0 − 2)w_{1}, (ix) w_{1}(1 − 0)u_{1}(1−0)u_{j}(0−2)w_{1}, (x) w_{1}(1−0)u_{1}(0−1)u_{j}(0−2)w_{1}, (xi) w_{1}(1−0)u_{1}(0−0)u_{j}(0−2)w_{1}, (xii) w_{1}(1 − 0)u_{1}(2 − 0)u_{j}(0 − 2)w_{1}.

If any one of (vii)–(xi) appears, then making respectively the transformations w_{1}(2 − 0)u_{1}(0 − 1)u_{j}(0 − 1)w_{1}, w_{1}(2 − 0)u_{1}(1 − 0)u_{j}(0 − 1)w_{1}, w_{1}(2 − 0)u_{1}(2 − 0)u_{j}(0 − 1)w_{1}, w_{1}(2 − 0)u_{1}(1 − 1)u_{j}(0 − 1)w_{1}, w_{1}(2 − 0)u_{1}(1 − 0)u_{j}(0 − 1)w_{1}, we get a 2-digraph D′ with the same mark sequence, but D and D′ have different numbers of arcs. Thus, D and D′ are non-isomorphic.

If (xii) and one of (i)-(v) appears simultaneously, we once again arrive to the conclusion that there exists a 2-digraph D′ with the mark sequence P, but D and D′ are non-isomorphic.

Thus, we are left with the case when (vi) and (xii) appear simultaneously, and also w_{q}(2 − 0)w_{i} for all 1 ≤ i < q ≤ r. But, then D is reducible having the irreducible components D_{1}, D_{2}, …, D_{r} with vertex sets V_{1} = {u_{1}, u_{2}, …, u_{s}, w_{1}}, V_{2} = {w_{2}}, …, V_{r} = {w_{r}} respectively.

(d) Let w_{1}(0−1)u_{1}. Since there are only six possibilities between w_{1} and w_{i}, therefore for any other vertex w_{i} in W, we have one of the following cases:

(i) w_{1}(2−1)w_{i}(2−0)u_{1}(1−0)w_{1}, (ii) w_{1}(1−1)w_{i}(2−0)u_{1}(1−0)w_{1}, (iii) w_{1}(1−0)w_{i}(2− 0)u_{1}(1 − 0)w_{1}, (iv) w_{1}(0 − 1)w_{i}(2 − 0)u_{1}(1 − 0)w_{1}, (v) w_{1}(0 − 0)w_{i}(2 − 0)u_{1}(1 − 0)w_{1}, (vi) w_{1}(0 − 2)w_{i}(2 − 0)u_{1}(1 − 0)w_{1}.

If any one of (i)–(v) appears, then making respectively the transformations w_{1}(1 − 0)w_{i}(1 − 0)u_{1}(0 − 0)w_{1}, w_{1}(0 − 1)w_{i}(1 − 0)u_{1}(0 − 0)w_{1}, w_{1}(0 − 0)w_{i}(1 − 0)u_{1}(0 − 0)w_{1}, w_{1}(0 − 2)w_{i}(1 − 0)u_{1}(0 − 0)w_{1}, w_{1}(0 − 1)w_{i}(1 − 0)u_{1}(0 − 0)w_{1}, gives a 2-digraph D′ with the same mark sequence, but the numbers of arcs in D and D′ are different so that D and D′ are non-isomorphic.

If (vi) appears in D, and also if w_{q}(2 − 0)w_{i} for all 1 ≤ i < q ≤ r, then D becomes reducible.

Now, for any other vertex u_{j} in U, there are only six possibilities between u_{1} and u_{j}, and we have one of the following cases:

(vii) w_{1}(0 − 1)u_{1}(0 − 2)u_{j}(0 − 2)w_{1}, (viii) w_{1}(0 − 1)u_{1}(1 − 1)u_{j}(0 − 2)w_{1}, (ix) w_{1}(0 − 1)u_{1}(1−0)u_{j}(0−2)w_{1}, (x) w_{1}(0−1)u_{1}(0−1)u_{j}(0−2)w_{1}, (ix) w_{1}(0−1)u_{1}(0−0)u_{j}(0−2)w_{1}, (xii) w_{1}(0 − 1)u_{1}(2 − 0)u_{j}(0 − 2)w_{1}.

If any one of (vii)–(xi) appears in D, then making respectively the transformations w_{1}(0−0)u_{1}(0−1)u_{j}(0−1)w_{1}, w_{1}(0−0)u_{1}(1−0)u_{j}(0−1)w_{1}, w_{1}(0−0)u_{1}(2−0)u_{j}(0−1)w_{1}, w_{1}(0 − 0)u_{1}(0 − 0)u_{j}(0 − 1)w_{1}, w_{1}(0 − 0)u_{1}(1 − 0)u_{j}(0 − 1)w_{1}, gives a 2-digraph D′ with the same mark sequence, but the numbers of arcs in D and D′ are different so that D is not isomorphic to D′.

If (xii) and any one of (i)–(v) appear simultaneously, then once again there exists a 2-digraph D′ with the same mark sequence, but D and D′ have different numbers of arcs so that D and D′ are non-isomorphic.

If (vi) and (xii) appear simultaneously, and also w_{q}(2 − 0)w_{i} for all 1 ≤ i < q ≤ r, then D is reducible.

Now, let D have exactly two vertices say u and v. The only irreducible mark sequences realizing D are [2, 2], and [1, 3]. Obviously the sequence [2, 2] has two non-isomorphic realizations namely u(0−0)v and u(1−1)v, and [1, 3] has the unique realization u(0−1)v. Thus P = [1, 3] is uniquely realizable.

If D has only one vertex, then P = [0], which evidently is uniquely realizable. □

Combining Theorem 3.3 and Theorem 3.4, we have the following result for 2-digraphs.

Theorem 3.5. The mark sequence P of a 2-digraph is uniquely realizable if and only if every irreducible component of P is of the form [0] or [1, 3].

We observe that in the mark sequence P = [4i−4]_{1}^{n} every irreducible component is [0], and thus P is uniquely realizable. We note that the mark sequences of tournaments are not uniquely realizable. To see this, consider the mark sequence P = [2, 4, 6] realizing the tournament T. The other 2-digraph D realized by P has vertex set {v_{1}, v_{2}, v_{3}} with v_{1}(0 − 0)v_{2}(0 − 0)v_{3}(2 − 0)v_{1}.

However, we observe that a mark sequence of a tournament T is uniquely realizable if and only if the mark sequence of the double tournament of T is uniquely realizable.

Now, we have the following generalization of Theorem 3.5, and the proof follows by using arguments as in Theorem 3.5.

Theorem 3.6. The mark sequence P of a k-digraph is uniquely realizable if and only if every irreducible component of P is of the form [0] or [1, 2k − 1].

Acknowledgements

The authors are thankful to the anonymous referee for his valuable suggestions and for providing an elegant proof of Theorem 2.2, which improved the presentation of the paper.

References

[1] P.Avery, Condition for a tournament score sequence to be simple, J. Graph Theory 4 (1980), 157– 164.

[2] P.Avery, Score sequences of oriented graphs, J.Graph Theory 15 (1991), 251–257.

[3] F.Harary, R.Z.Norman and D.Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley and Sons, New York (1965).

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

[5] J.W.Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York (1968).

[6] S.Pirzada, Simple score sequences in oriented graphs, Novi Sad J. Mathematics 33 (2003), 25–29.

[7] S.Pirzada and T.A.Naikoo, Inequalities for marks in digraphs, Mathematical Inequalities and Applications 9 (2006), 189–198.

[8] S.Pirzada, On oriented graph scores, to appear.