Conditions on the regularity of balanced $c$-partite tournaments for the existence of strong subtournaments with high minimum degree

Autor:	Figueroa, Ana Paulina, Montellano-Ballesteros, Juan José, Olsen, Mika
Rok vydání:	2020
Předmět:	Mathematics - Combinatorics 05C20 05C35
Druh dokumentu:	Working Paper
Popis:	We consider the following problem posed by Volkmann in 2007: How close to regular must a c-partite tournament be, to secure a strongly connected subtournament of order $c$? We give sufficient conditions on the regularity of balanced $c$-partite tournaments to assure the existence of strong maximal subtournament with minimum degree at least $\left\lfloor \frac{c-2}{4}\right\rfloor+1$. We obtain this result as an application of counting the number of subtournaments of order $c$ for which a vertex has minimum out-degree (resp. in-degree) at most $q\geq 0$. Comment: 13 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2010.09835 Zobrazit plný text záznamu View this record from Arxiv