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
    0 references
    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
    0 references

    Identifiers