Multipartite digraphs and mark sequences

Umatul Samee

Kragujevac Journal of Mathematics, Tome 35 (2011) no. 1, p. 151

Résumé

A $k$-partite $2$-digraph (or briefly multipartite 2-digraph(M2D)) is an orientation of a $k$-partite multigraph that is without loops and contains at most $2$ edges between any pair of vertices from distinct parts. Let $D = D(X_{1}, X_{2},\ldots, X_{k})$ be a $k$-partite $2$-digraph with parts $X_{i} = \{x_{i1}, x_{i2},\ldots, x_{in_{i}}\}$, $1 \leq i\leq k$. Let $d_{x_{ij}}^{+}$ and $d_{x_{ij}}^{-}$, $1eq jeq n_{i}$, be respectively the outdegree and indegree of a vertex $x_{ij}n X_{i}$. Define $p_{x_{ij}}$ (or simply $p_{ij}) =2eft(um_{t=1,teq i}^{k}n_{t}\right)+d_{x_{ij}}^{+}-d_{x_{ij}}^{-}$ as the mark (or $r$-score) of $x_{ij}$. In this paper, we characterize the marks of $k$-partite $2$-digraphs and obtain constructive and existence criterion for $k$ sequences of non-negative integers in non-decreasing order to be the mark sequences of some $k$-partite $2$-digraph.

Détail

Classification : 05C20
Keywords: Multipartite digraphs, Oriented graphs, Tournaments, Mark sequences, Oriented triples