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

From MaRDI portal





scientific article; zbMATH DE number 5249208
Language Label Description Also known as
default for all languages
No label defined
    English
    Almost regular \(c\)-partite tournaments contain a strong subtournament of order \(c\) when \(c\geqslant 5\)
    scientific article; zbMATH DE number 5249208

      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