Séminaire Lotharingien de Combinatoire, B55c (2006), 13 pp.

S. Pirzada and U. Samee

Mark Sequences in Digraphs

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 mark sequences in k-digraphs and uniquely realizable mark sequences in 2-digraphs.

Received: September 21, 2005. Revised: June 1, 2006. Accepted: July 3, 2006.

The following versions are available: