×

On imbalances in oriented multipartite graphs. (English) Zbl 1268.05092

Summary: An oriented \(k\)-partite graph (multipartite graph) is the result of assigning a direction to each edge of a simple \(k\)-partite graph. Let \(D(V_1, V_2, \ldots, V_k)\) be an oriented \(k\)-partite graph, and let \(d^{+}_{v_{ij}}\) and \(d^{-}_{v_{ij}}\) be respectively the outdegree and indegree of a vertex \(v_{ij}\) in \(V_i\). Define \(b_{v_{ij}}\) (or simply \(b_{ij}\) as \(b_{ij} = d^{+}_{v_{ij}}-d^{-}_{v_{ij}}\) as the imbalance of the vertex \(v_{ij}\).
In this paper, we characterize the imbalances of oriented \(k\)-partite graphs and give a constructive and existence criteria for sequences of integers to be the imbalances of some oriented \(k\)-partite graph. Also, we show the existence of an oriented \(k\)-partite graph with the given imbalance set.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: EMIS