Score sets in oriented \(k\)-partite graphs (Q2370389)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Score sets in oriented \(k\)-partite graphs |
scientific article |
Statements
Score sets in oriented \(k\)-partite graphs (English)
0 references
25 June 2007
0 references
Let \(D(U_1,U_2,\dots, U_n)\) be an oriented \(k\)-partite graph with \(|U_i|= n_i\), \(1\leq i\leq k\). Then the score of a vertex \(u_i\in U_i\) is defined by \(a_i= \sum^k_{\substack{ t=1\\ t\neq i}} n_t+ d^+_{u_i}- d^-_{u_i}\), where \(d^+_{u_i}\) and \(d^-_{u_i}\) are the outdegree and indegree of \(u_i\). The set \(A\) of distinct scores of the vertices of \(D\) is called its score set. Here the authors prove that if \(a_1\) is a nonnegative integer, \(a_i\) \((2\leq i\leq n-1)\) are even positive integers and \(a_n\) is any positive integer, then for every \(n\geq k\geq 3\), there exists an oriented \(k\)-partite graph with score set \(A= \{a_1, \sum^2_{i=1} a_i,\dots, \sum^n_{i=1} a_i\}\), except when \(a_i= 0\), \(a_k= 1\), and \(n= k\geq 3\).
0 references
tournament
0 references
score sequence
0 references
oriented \(k\)-partite graph
0 references