2021/08/02 by Hortensia Galeana‐Sánchez, Hortensia Galeana-Sánchez, Galeana-Sánchez, Hortensia +2
Computer Science · Mathematics · #05C15 #05C20 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C20 #msc:05C69
paper · pdf · doi:10.48550/arxiv.2108.01168
arXiv admin note: text overlap with arXiv:2105.00044
arxiv created 2021/08/02 · openalex publication_date 2021/08/02 · arxiv updated 2021/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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=(x0, … , xn) is a walk in D, and i ∈ \ 0, … , n-1 \, we say that there is an obstruction on xi whenever (ρ(xi-1, xi), ρ(xi, xi+1)) ∉ A(H) (when x0 = xn the indices are taken modulo n). We denote by OH(W) the set \ i ∈ \0, … , n-1 \ : there is an obstruction on xi \. The H-length of W, denoted by lH(W), is defined by |OH(W)|+1 whenever x0 ≠ xn, or |OH(W)| in 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 as kernel, k-kernel, kernel by monochromatic paths, kernel by properly colored paths, and H-kernel. In this paper, 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 its applications and theoretical results. We will show several conditions that guarantee the existence of (k,H)-kernel in tournaments, r-transitive digraphs, r-quasi-transitive digraphs, multipartite tournaments, and local tournaments.