$H$-kernels by walks in subdivision digraph

Document Type: Research Paper


1 Ciudad Universitaria,Coyoacán 04510,Ciudad de México, México

2 Universidad Autónoma del Estado de México, Estado de México

3 Department of Mathematics, Science Faculty, UNAM



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)‎. ‎A directed walk $W$ in $D$ is said to be an $H$-walk if and only if the consecutive colors encountered on $W$ form a directed walk in $H$‎. ‎A subset $N$ of the vertices of $D$ is said to be an $H$-kernel by walks if (1) for every pair of different vertices in $N$ there is no $H$-walk between them ($N$ is $H$-independent by walks) and (2) for each vertex $u$ in $V$($D$)-$N$ there exists an $H$-walk from $u$ to $N$ in $D$ ($N$ is $H$-absorbent by walks)‎. ‎Suppose that $D$ is a digraph possibly infinite‎. ‎In this paper we will work with the subdivision digraph $S_H$($D$) of $D$‎, ‎where $S_H$($D$) is an $H$-colored digraph defined as follows‎: ‎$V$($S_H$($D$)) = $V$($D$) $\cup$ $A$($D$) and $A$($S_H$($D$)) = \{($u$,$a$)‎ : ‎$a$ = ($u$,$v$) $\in$ $A$($D$)\} $\cup$ \{($a$,$v$)‎ : ‎$a$ = ($u$,$v$) $\in$ $A$($D$)\}‎, ‎where ($u$‎, ‎$a$‎, ‎$v$) is an $H$-walk in $S_H$($D$) for every $a$ = ($u$,$v$) in $A$($D$)‎. ‎We will show sufficient conditions on $D$ and on $S_H$($D$) which guarantee the existence or uniqueness of $H$-kernels by walks in $S_H$($D$)‎.