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