$(k,H)$-kernels in nearly tournaments

Galeana-Sánchez, Hortensia ; Tecpa-Galván, Miguel 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 639-662

Résumé

Let H be a digraph, possibly with loops, D a digraph without loops, and ρ : A(D) → V(H) a coloring of A(D) (D is said to be an H-colored digraph). If W=(x_0, …, x_n) is a walk in D, and i ∈{ 0, …, n-1 }, then we say that there is an obstruction on x_i whenever (ρ(x_i-1, x_i), ρ (x_i, x_i+1)) ∉ A(H) (when x_0 = x_n the indices are taken modulo n). We denote by O_H(W) the set { i ∈{0, …, n-1 } : there is an obstruction on x_i}. The H-length of W, denoted by l_H(W), is defined by |O_H(W)| if W is closed or |O_H(W)|+1 in the other case. A (k, H)-kernel of an H-colored digraph D (k ≥ 2) is a subset of vertices of D, say S, such that, for every pair of different vertices in S, every path between them has H-length at least k, and for every vertex x ∈ V(D) ∖ S there exists an xS-path with H-length at most k-1. This concept widely generalize previous nice concepts such as kernel, k-kernel, kernel by monochromatic paths, kernel by properly colored paths, and H-kernel. In this paper, we introduce the concept of (k,H)-kernel and we will study the existence of (k,H)-kernels in interesting classes of digraphs, called nearly tournaments, which have been large and widely studied due to its applications and theoretical results. We will show several conditions that guarantee the existence of a (k,H)-kernel in tournaments, r-transitive digraphs, r-quasi-transitive digraphs, multipartite tournaments, and local tournaments. As a consequence, previous results for k-kernels and kernels by alternating paths will be generalized, and some conditions for the existence of kernels by monochromatic paths and H-kernels in nearly tournaments will be shown.

Détail

Keywords: kernel, $k$-kernel, $H$-kernel, $H$-coloring, kernel by monochromatic paths, kernel by alternating paths

Bibliographie

[1] C. Andenmatten, H-distance, H-A-kernel and in-state splitting in H-colored graphs and digraphs (MSc Thesis supervised by H. Galeana-Sánchez and J. Pach, École Polytechnique Fédérale de Lausanne, Switzerland, 2019).

[2] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math. 307 (2007) 2276–2289. https://doi.org/10.1016/j.disc.2006.09.042

[3] J. Bang-Jensen, The structure of strong arc-locally semicomplete digraphs, Discrete Math. 283 (2004) 1–6. https://doi.org/10.1016/j.disc.2004.01.011

[4] J. Bang-Jensen, Y. Guo, G. Gutin and L. Volkmann, A classification of locally semicomplete digraphs, Discrete Math. 167–168 (1997) 101–114. https://doi.org/10.1016/S0012-365X(96)00219-1

[5] J. Bang-Jensen and G. Gutin, Classes of Directed Graphs (Springer, 2018). https://doi.org/10.1007/978-3-319-71840-8

[6] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Edition (Springer, London, 2000). https://doi.org/10.1007/978-1-84800-998-1

[7] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141–161. https://doi.org/10.1002/jgt.3190200205

[8] J. Bang-Jensen, J. Huang and E. Prisner, In-tournament digraphs, J. Combin. Theory Ser. B 59 (1993) 267–287. https://doi.org/10.1006/jctb.1993.1069

[9] C. Berge, Graphs and Hypergraphs (North-Holland Publishing Co., Amsterdam, 1985).

[10] V. Chvátal, On the computational complexity of finding a kernel, Report CRM300 (Centre de Recherches Mathématiques, Université de Montréal, 1973).

[11] V. Chvátal and L. Lovasz, Every directed graph has a semi-kernel, in: Hypergraph Seminar, Part II: Graphs, Matroids, Designes, C. Berge and D. Ray-Chandhuri (Ed(s)), (Lecture Notes in Mathematics 411, Springer-Verlag 1974) 175. https://doi.org/10.1007/BFb0066192

[12] N. Creignou, The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness, Theoret. Comput. Sci. 145 (1995) 111–145. https://doi.org/10.1016/0304-3975(94)00182-I

[13] P. Delgado-Escalante, H. Galeana-Sánchez and S. Arumugam, Restricted domination in arc-colored digraphs, AKCE Int. J. Graphs Comb. 11 (2014) 95–104.

[14] P. Delgado-Escalante, H. Galeana-Sánchez and E. O'Reilly-Regueiro, Alternating kernels, Discrete Appl. Math. 236 (2018) 153–164. https://doi.org/10.1016/j.dam.2017.10.013

[15] Y. Dimopoulos and V. Magirou, A graph theoretic approach to default logic, Inform. Comput. 112 (1994) 239–256. https://doi.org/10.1006/inco.1994.1058

[16] Y. Dimopoulos and A. Torres, Graph theoretical structures in logic programs and default theories, Theoret. Comput. Sci. 170 (1996) 209–244. https://doi.org/10.1016/S0304-3975(96)80707-9

[17] P. Duchet, Graphes noyau-parfaits, Ann. Discrete Math. 9 (1980) 93–101. https://doi.org/10.1016/S0167-5060(08)70041-4

[18] A.S. Fraenkel, Combinatorial game theory foundations applied to digraph kernels, Electron. J. Combin. 4 (2) (1997) #R10. https://doi.org/10.37236/1325

[19] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in generalizations of transitive digraphs, Discuss. Math. Graph Theory 31 (2011) 293–312. https://doi.org/10.7151/dmgt.1546

[20] H. Galeana-Sánchez and C. Henrández-Cruz, k-kernels in k-transitive and k-quasi-transitive digraphs, Discrete Math. 312 (2012) 2522–2530. https://doi.org/10.1016/j.disc.2012.05.005

[21] H. Galeana-Sánchez, C. Hernández-Cruz and S. Arumugam, k-kernels in multipartite tournaments, AKCE Int. J. Graphs Comb. 8 (2011) 181–198.

[22] H. Galeana-Sánchez and R. Sánchez-López, H-kernels and H-obstructions in H-colored digraphs, Discrete Math. 338 (2015) 2288–2294. https://doi.org/10.1016/j.disc.2015.05.021

[23] H. Galeana-Sánchez and R. Sánchez-López, Richardson's theorem in H-coloured digraphs, Graphs Combin. 32 (2016) 629–638. https://doi.org/10.1007/s00373-015-1609-3

[24] H. Galeana-Sánchez and R. Strausz, On panchromatic digraphs and the panchromatic number, Graphs Combin. 31 (2015) 115–125. https://doi.org/10.1007/s00373-013-1367-z

[25] H. Galeana-Sánchez and R. Strausz, On panchromatic patterns, Discrete Math. 339 (2016) 2536–2542. https://doi.org/10.1016/j.disc.2016.03.014

[26] H. Galeana-Sánchez and M. Tecpa-Galván, \mathscr{H}-panchromatic digraphs, AKCE Int. J. Graphs Comb. 17 (2020) 303–313. https://doi.org/10.1016/j.akcej.2019.05.005

[27] H. Galeana-Sánchez and M. Toledo, New classes of panchromatic digraphs, AKCE Int. J. Graphs Comb. 12 (2015) 261–270. https://doi.org/10.1016/j.akcej.2015.11.006

[28] P. Garcia-Vázquez and C. Hernández-Cruz, Some results on 4-transitive digraphs, Discuss. Math. Graph Theory 37 (2017) 117–129. https://doi.org/10.7151/dmgt.1922

[29] A. Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les de maniere a obtenir le graphe d'une relation d'ordre, C.R. Acad. Sci. Paris 254 (1962) 1370–1371.

[30] S. Heard and J. Huang, Disjoint quasi-kernels in digraphs, J. Graph Theory 58 (2008) 251–260. https://doi.org/10.1002/jgt.20310

[31] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205–219. https://doi.org/10.7151/dmgt.1613

[32] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and k-quasi-transitive digraphs, Discrete Math. 312 (2012) 2522–2530. https://doi.org/10.1016/j.disc.2012.05.005

[33] D. König, Theorie der Endlichen und Unendlichen Graphen (Reprinted from AMS Chelsea Publishing Company, Providence, Rhode Island, 1950).

[34] M. Kwaśnik, On (k,l)-kernels in graphs and their products, Ph.D. Thesis (Technical University of Wroc\l aw, Wroc\l aw, 1980).

[35] V. Linek and B. Sands, A note on paths in edge-colored tournaments, Ars Combin. 44 (1996) 225–228.

[36] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).

[37] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).

[38] K.B. Reid, Monotone reachability in arc-colored tournaments, Congr. Numer. 146 (2000) 131–141.

[39] S. Szeider, Finding paths in graphs avoiding forbidden transitions, Discrete Appl. Math. 126 (2003) 261–273. https://doi.org/10.1016/S0166-218X(02)00251-2

[40] R. Wang, (k-1)-kernels in strong k-transitive digraphs, Discuss. Math. Graph Theory 35 (2015) 229–235. https://doi.org/10.7151/dmgt.1787

[41] R. Wang and H. Zhang, (k+1)-kernels and the number of k-kings in k-quasi-transitive digraphs, Discrete Math. 338 (2015) 114–121. https://doi.org/10.1016/j.disc.2014.08.009