×

Conditions on the regularity of balanced \(c\)-partite tournaments for the existence of strong subtournaments with high minimum degree. (English) Zbl 1490.05093

Summary: We consider the following problem posed by L. Volkmann [Discrete Math. 307, No. 24, 3097–3129 (2007; Zbl 1134.05033)]: How close to regular must ac-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 ensure the existence of a strong maximal subtournament with minimum degree at least \(\lfloor\frac{c-2}{4}\rfloor+1\). We obtain 4 this result as an application of counting the number of subtournaments of order \(c\) for which a vertex has minimum out-degree (respectively, indegree) at most \(q\geq 0\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C07 Vertex degrees

Citations:

Zbl 1134.05033

References:

[1] J. Bang-Jensen and G. Gutin,Digraphs: Theory, Algorithms and Applications, Springer, London, 2001. · Zbl 0958.05002
[2] A. P. Figueroa, J. J. Montellano Ballesteros and M. Olsen, Strong subtournaments and cycles of multipartite tournaments,Discrete Math.339(2016), 2793-2803. · Zbl 1339.05158
[3] L. Volkmann, Strong subtournaments of multipartite tournaments,Australas. J. Combin.20(1999), 189-196. · Zbl 0935.05051
[4] L. Volkmann, Multipartite tournaments: A survey,Discrete Math.307(2007), 3097-3129. · Zbl 1134.05033
[5] L. Volkmann and S. Winzen, Almost regularc-partite tournaments contain a strong subtournament of ordercwhenc≥5,Discrete Math.308(2008), 1710- 1721. · Zbl 1139.05028
[6] G. Xu, S. Li, H. Li and Q. Guo, Strong subtournaments of order image containing a given vertex in regularc-partite tournaments withc≥16,Discrete Math.311 (2011), 2272-2275 · Zbl 1283.05119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.