2019/07/26 by Abderrahim Boussaïri, Boussaïri, Abderrahim, Soufiane Lakhlifi +3
Computer Science · Social Sciences · Decision Sciences · #Advanced Graph Theory Research #School Choice and Performance #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1907.11777
An n-tournament T with vertex set V is simple if there is no subset M of V such that 2≤ \vert M \vert ≤ n-1 and for every x∈ V∖ M, either M→ x or x → M. The simplicity index of an n-tournament T is the minimum number s(T) of arcs whose reversal yields a non-simple tournament. Müller and Pelant (1974) proved that s(T)≤(n-1)/(2), and that equality holds if and only if T is doubly regular. As doubly regular tournaments exist only if n≡ 3\pmod4, s(T)