首页|H-kernels in H-colored digraphs without (?(1),?,?(2))-H-subdivisions of (C)over right arrow(3)
H-kernels in H-colored digraphs without (?(1),?,?(2))-H-subdivisions of (C)over right arrow(3)
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Let H be a digraph possibly with loops and D a digraph without loops with a coloring of its arcs c : A(D)& nbsp;-> V (H) ( D is said to be an H-colored digraph). A directed path W in D is said to be an H-path if and only if the consecutive colors encountered on W form a directed walk in H. A subset N of vertices of D is said to be an H-kernel if (1) for every pair of different vertices in N there is no H-path between them and (2) for every vertex u in V (D ) \ N there exists an H-path in D from u to N. Under this definition an H-kernel is a kernel whenever A(H) = empty set . The color-class digraph C-C (D ) of D is the digraph whose vertices are the colors represented in the arcs of D and (i, j) is an element of & nbsp;A (C-C (D )) if and only if there exist two arcs, namely (u, v ) and (v , w ) in D , such that (u, v ) has color i and (v , w ) has color j. Since not every H-colored digraph has an H-kernel and V (C-C(D)) = V (H) , the natural question is: what structural properties of C-C(D), with respect to the H-coloring, imply that D has an H-kernel?& nbsp;In this paper we investigate the problem of the existence of an H-kernel by means of a partition xi of V(H) and a partition {xi(1), xi(2)} of xi. We establish conditions on the directed cycles and the directed paths of the digraph D , with respect to the partition {xi(1), xi(2)}. In particular we pay attention to some substructures produced by the partitions xi and {xi(1), xi(2}), namely (xi(1),xi, xi(2)) -H-subdivisions of (C)over right arrow(3) and (xi(1), xi, xi(2)) -H-subdivisions of (P)over right arrow(3) .& nbsp;We give some examples which show that each hypothesis in the main result is tight. (C)& nbsp;2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier
