$(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