×

On the existence and number of (\(k+1\))-kings in \(k\)-quasi-transitive digraphs. (English) Zbl 1281.05068

Summary: Let \(D=(V(D),A(D))\) be a digraph and \(k\geq 2\) an integer. We say that \(D\) is \(k\)-quasi-transitive if for every directed path \((v_0,v_1,\dots ,v_k)\) in \(D\) we have \((v_0,v_k)\in A(D)\) or \((v_k,v_0)\in A(D)\). Clearly, a 2-quasi-transitive digraph is a quasi-transitive digraph in the usual sense. J. Bang-Jensen and G. Gutin [in: Digraphs. Theory, Algorithms and Applications. London: Springer (2002; Zbl 1001.05002)] proved that a quasi-transitive digraph \(D\) has a \(3\)-king if and only if \(D\) has a unique initial strong component, and if \(D\) has a \(3\)-king and the unique initial strong component of \(D\) has at least three vertices, then \(D\) has at least three \(3\)-kings.
In this paper we prove the following generalization: a \(k\)-quasi-transitive digraph \(D\) has a \((k+1)\)-king if and only if \(D\) has a unique initial strong component, and if \(D\) has a \((k+1)\)-king, then either all the vertices of the unique initial strong components are \((k+1)\)-kings or the number of \((k+1)\)-kings in \(D\) is at least \((k+2)\). Also, we obtain new results on the minimum number of \(3\)-kings in quasi-transitive digraphs.

MSC:

05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1001.05002
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs. Theory, Algorithms and Applications (2002), Springer-Verlag · Zbl 1001.05002
[2] Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, Journal of Graph Theory, 20, 2, 141-161 (1995) · Zbl 0832.05048
[3] Bang-Jensen, J.; Huang, J., Kings in quasi-transitive digraphs, Discrete Mathematics, 185, 19-27 (1998) · Zbl 0955.05048
[4] Boesch, F.; Tindell, R., Robbins’s theorem for mixed multigraphs, The American Mathematical Monthly, 87, 716-719 (1980) · Zbl 0453.05026
[5] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer-Verlag · Zbl 1134.05001
[6] Galeana-Sánchez, H.; Goldfeder, I. A.; Urrutia, I., On the structure of 3-quasi-transitive digraphs, Discrete Mathematics, 310, 2495-2498 (2010) · Zbl 1213.05112
[7] Galeana-Sánchez, H.; Hernández-Cruz, C., \(k\)-kernels in generalizations of transitive digraphs, Discussiones Mathematicae Graph Theory, 31, 2, 293-312 (2011) · Zbl 1234.05113
[8] Galeana-Sánchez, H.; Hernández-Cruz, C., \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs, Discrete Mathematics, 312, 16, 2522-2530 (2012) · Zbl 1246.05067
[9] Gutin, G. M., The radii of \(n\)-partite tournaments, Mathematical Notes, 40, 743-744 (1986) · Zbl 0691.05016
[10] Gutin, G.; Yeo, A., Kings in semicomplete multipartite digraphs, Journal of Graph Theory, 33, 177-183 (2000) · Zbl 0944.05053
[11] Jacob, H.; Menyiel, H., About quasi-kernels in a digraph, Discrete Mathematics, 154, 279-280 (1996) · Zbl 0854.05055
[12] Koh, K. M.; Tan, B. P., Kings in multipartite tournaments, Discrete Mathematics, 147, 171-183 (1995) · Zbl 0841.05038
[13] Koh, K. M.; Tan, B. P., Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Mathematics, 154, 281-287 (1996) · Zbl 0851.05053
[14] Koh, K. M.; Tan, B. P., The number of kings in a multipartite tournament, Discrete Mathematics, 167-168, 411-418 (1997) · Zbl 0871.05028
[15] Landau, H. G., On dominance relations and the structure of animal societies III: the condition for a score structure, Bulletin of Mathematical Biophysics, 15, 143-148 (1953)
[16] Petrovic, V.; Thomassen, C., Kings in \(k\)-partite tournaments, Discrete Mathematics, 98, 237-238 (1991) · Zbl 0751.05047
[17] Petrovic, V.; Treml, M., 3-kings in 3-partite tournaments, Discrete Mathematics, 308, 277-286 (2008) · Zbl 1130.05029
[18] Tan, B. P., On the 3-kings and 4-kings in multipartite tournaments, Discrete Mathematics, 306, 2702-2710 (2006) · Zbl 1106.05044
[19] Wang, S.; Wang, R., Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs, Discrete Mathematics, 311, 282-288 (2010) · Zbl 1222.05090
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.