MARK SEQUENCES IN 3-PARTITE 2-DIGRAPHS

MARK SEQUENCES IN 3-PARTITE 2-DIGRAPHS

A 3-partite 2-digraph is an orientation of a 3-partite multi-graph that is without loops and contains at most two edges between any pair of vertices from distinct parts. Let D(X, Y, Z) be a 3-partite 2-digraph with ${\mid}X{\mid}=l,\;{\mid}Y{\mid}=m,\;{\mid}Z{\mid}=n$. For any vertex v in D(X, Y, Z), let $d^+_{\nu}\;and\;d^-_{\nu}$ denote the outdegree and indegree respectively of v. Define $p_x=2(m+n)+d^+_x-d^-_x,\;q_y=2(l+n)+d^+_y-d^-_y\;and\;r_z=2(l+m)+d^+_z-d^-_z$ as the marks (or 2-scores) of x in X, y in Y and z in Z respectively. In this paper, we characterize the marks of 3-partite 2-digraphs and give a constructive and existence criterion for sequences of non-negative integers in non-decreasing order to be the mark sequences of some 3-partite 2-digraph.