Alternating Domination in Arc-Colored Digraphs

Abstract

An arc-colored digraph \(D\) is called alternating whenever \(\{(u, v), (v, w)\} \subseteq A(D)\) implies that the color assigned to \((u, v)\) is different from the color of \((v, w)\). In arc-colored digraphs, a set of vertices \(N\) is said to be a kernel by alternating paths whenever it is an independent and dominating set by alternating directed paths (there is no alternating directed path between every pair of its vertices and for every vertex not in \(N\), there exists an alternating path from it to some vertex in \(N\)). With this new concept, we generalize the concept of kernel in digraphs. In this paper, we prove the existence of alternating kernels in possibly infinite arc-colored digraphs with some coloration properties. We also state a bilateral relation between the property of every induced subdigraph of an arc-colored digraph \(D\) of having a kernel by alternating paths and the property of every induced subdigraph of the non-colored digraph \(D\) of having a kernel, with this we enounce several sufficient conditions for \(D\) to have an alternating kernel. Previous results on kernels are generalized.