2021/04/30 by Hortensia Galeana‐Sánchez, Galeana-Sánchez, Hortensia, Miguel Tecpa-Galván +1
Computer Science · Mathematics · #05C15 #05C20 #05C69 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2105.00044
openalex publication_date 2021/04/30 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Let H be a digraph possibly with loops and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). If W=(x0,…,xn) is an open walk in D and i∈ \1,…,n-1\, we say that there is an obstruction on xi if (color(xi-1,xi),color(xi,xi+1))∉ A(H). If S⊆ V(D), we say that S is a (k,l,H)-kernel by walks if for every pair of different vertices in S, every walk between them has at least k-1 obstructions, and for every x∈ V(D)∖ S there exists an xS-walk with at most l-1 obstructions. If D is an H-colored digraph, an H-class partition is a partition \mathscrF of A(D) such that, for every \(u,v),(v,w)\⊆ A(D), (color(u,v),color(v,w))∈ A(H) iff there exists F in \mathscrF such that \(u,v),(v,w)\⊆ F. The H-class digraph relative to \mathscrF, denoted by C_\mathscrF(D), is the digraph such that V(C_\mathscrF(D))=\mathscrF, and (F,G)∈ A(C_\mathscrF(D)) if and only if there exist (u,v)∈ F and (v,w)∈ G with \u,v,w\⊆ V(D). We will show sufficient conditions on \mathscrF and C_\mathscrF(D) to guarantee the existence of (k,l,H)-kernels by walks in H-colored digraphs, and we will show that some conditions are tight. For instance, we will show that if an H-colored digraph D has an H-class partition in which every class induces a strongly connected digraph, and has an obstruction-free vertex, then for every k≥ 2, D has a (k,k-1,H)-kernel by walks. Despite the fact that finding (k,l)-kernels in arbitrary H-colored digraphs is an NP-complete problem, some hypothesis presented in this paper can be verified in polynomial time.