Source author record

Cherifa Ben Salha

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Decomposability and co-modular indices of tournaments

Given a tournament $T$ , a module of $T$ is a subset $X$ of $V(T)$ such that for $x, y\in X$ and $v\in V(T)\setminus X$ , $(x,v)\in A(T)$ if and only if $(y,v)\in A(T)$ . The trivial modules of $T$ are $\emptyset$ , $\{u\}$ $(u\in V(T))$ and $V(T)$ . The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of $T$ , denoted by $δ(T)$ , is the smallest number of arcs of $T$ that must be reversed to make $T$ indecomposable. The first author conjectured that for $n \geq 5$ , we have $δ(n) = \left\lceil \frac{n+1}{4} \right\rceil$ , where $δ(n)$ is the maximum of $δ(T)$ over the tournaments $T$ with $n$ vertices. In this paper we prove this conjecture by introducing the co-modular index of a tournament $T$ , denoted by $Δ(T)$ , as the largest number of disjoint co-modules of $T$ , where a co-module of $T$ is a subset $M$ of $V(T)$ such that $M$ or $V(T) \setminus M$ is a nontrivial module of $T$ . We prove that for $n \geq 3$ , we have $Δ(n) = \left\lceil \frac{n+1}{2} \right\rceil$ , where $Δ(n)$ is the maximum of $Δ(T)$ over the tournaments $T$ with $n$ vertices. Our main result is the following close relationship between the above two indices: for every tournament $T$ with at least $5$ vertices, we have $δ(T) = \left\lceil \frac{Δ(T)}{2} \right\rceil$ . As a consequence, we obtain $δ(n) = \left\lceil \frac{Δ(n)}{2} \right\rceil = \left\lceil \frac{n+1}{4} \right\rceil$ for $n \geq 5$ , and we answer some further related questions.

preprint2021arXiv

Tournaments with maximal decomposability

Given a tournament $T$ , a module of $T$ is a subset $M$ of $V(T)$ such that for $x, y\in M$ and $v\in V(T)\setminus M$ , $(x,v)\in A(T)$ if and only if $(y,v)\in A(T)$ . The trivial modules of $T$ are $\emptyset$ , $\{u\}$ $(u\in V(T))$ and $V(T)$ . The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of $T$ , denoted by $δ(T)$ , is the smallest number of arcs of $T$ that must be reversed to make $T$ indecomposable. In a previous paper, we proved that for $n \geq 5$ , we have $δ(n) = \left\lceil \frac{n+1}{4} \right\rceil$ , where $δ(n)$ is the maximum of $δ(T)$ over the tournaments $T$ with $n$ vertices. In this paper, we characterize the tournaments $T$ with $δ$ -maximal decomposability, i.e., such that $δ(T)=δ(\vert T\vert)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.