TY - JOUR
ID - 24341
TI - $H$-kernels by walks in subdivision digraph
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Galeana-Sánchez, Hortensia
AU - Rojas-Monroy, Roc´ıo
AU - Sanchez Lopez, Maria del Rocio
AU - Zavala-Santana, Berta
AD - Ciudad Universitaria,Coyoacán
04510,Ciudad de México, México
AD - Universidad Autónoma del Estado de México, Estado de México
AD - Department of Mathematics, Science Faculty, UNAM
Y1 - 2020
PY - 2020
VL - 9
IS - 2
SP - 61
EP - 75
KW - Kernel
KW - Kernel by monochromatic paths
KW - $H$-kernel by walks
KW - subdivision digraph
DO - 10.22108/toc.2020.107875.1529
N2 - 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$).
UR - http://toc.ui.ac.ir/article_24341.html
L1 - http://toc.ui.ac.ir/article_24341_2a0223bff824f193c06ca18595725ca4.pdf
ER -