Almost regular \(c\)-partite tournaments contain a strong subtournament of order \(c\) when \(c\geqslant 5\) (Q2477396)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Almost regular \(c\)-partite tournaments contain a strong subtournament of order \(c\) when \(c\geqslant 5\)
scientific article

    Statements

    Almost regular \(c\)-partite tournaments contain a strong subtournament of order \(c\) when \(c\geqslant 5\) (English)
    0 references
    0 references
    0 references
    13 March 2008
    0 references
    Let \(D\) denote a directed graph with vertex set \(V\). Define the global irregularity of \(D\) to be \[ I_g(D)=\max\{d^+(x),d^-(x):x\in V\}-\min\{d^+(x),d^-(x):x\in V\}. \] The main result is that, if \(D\) is an oriented complete \(c\)-partite graph for \(c\geq5\) and if \(i_g(D)\leq1\), then \(D\) contains a strongly connected subtournament of order \(c\). This proves a conjecture by the first author [Australas. J. Comb. 20, 189--196 (1999; Zbl 0935.05051)].
    0 references
    subtournaments
    0 references
    multipartite tournaments
    0 references
    regular multipartite tournaments
    0 references

    Identifiers