simplicity index of tournaments

An $n$-tournament $T$ with vertex set $V$ is simple if there is no subset $M$ of $V$ such that $2\leq \left \vert M\right \vert \leq n-1$ and for every $x\in V\setminus M$, either $M\rightarrow x$ or $x\rightarrow M$. The simplicity index of an $n$-tournament $T$ is the minimum number $s(T)$ of arcs...

Full description

Saved in:
Bibliographic Details
Published in:Contributions to discrete mathematics 2022-01, Vol.17 (2), p.172-186
Main Authors: Boussaïri, Abderrahim, Lakhlifi, Soufiane, Talbaoui, Imane
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An $n$-tournament $T$ with vertex set $V$ is simple if there is no subset $M$ of $V$ such that $2\leq \left \vert M\right \vert \leq n-1$ and for every $x\in V\setminus M$, either $M\rightarrow x$ or $x\rightarrow M$. The simplicity index of an $n$-tournament $T$ is the minimum number $s(T)$ of arcs whose reversal yields a nonsimple tournament. Müller and Pelant (1974) proved that $s(T)\leq(n-1)/2$, and that equality holds if and only if $T$ is doubly regular. As doubly regular tournaments exist only if $n\equiv 3\pmod{4}$, $s(T)
ISSN:1715-0868
1715-0868
DOI:10.55016/ojs/cdm.v17i2.72680