H-KERNELS IN UNIONS OF H-COLORED QUASI-TRANSITIVE DIGRAPHS
Por:
Manuel Campero-Alonzo, Jose, Sanchez-Lopez, Rocio
Publicada:
1 ene 2021
Resumen:
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). For an arc (x, y) of D, its color is denoted by c(x,
y). A directed path W = (v(0), ..., v(n)) in an H-colored digraph D will
be called H-path if and only if (c(v(0), v(1)), ..., c(v(n-1), v(n))) is
a directed walk in H. In W, we will say that there is an obstruction on
v(i) if (c(v(i-1), v(i)), c(v(i), v(i-1))) is not an element of A(H) (if
v(0) = v(n) we will take indices modulo n). A subset N of V(D) is said
to be an H-kernel in D if for every pair of different vertices in N
there is no H-path between them, and for every vertex u in
V(D)textbackslashN there exists an H-path in D from u to N. Let D be
an arc-colored digraph. The color-class digraph of D, l(C)(D), is the
digraph such that V(l(C)(D)) = {c(a) : a is an element of A(D) and
(i, j) is an element of A(l(C)(D)) if and only if there exist two arcs,
namely (u, v) and (v, w) in D, such that c(u, v) = i and c(v, w) = j.
The main result establishes that if D = D-1 boolean OR D-2 is an
H-colored digraph which is a union of asymmetric quasi-transitive
digraphs and {V-1, ..., V-k is a partition of V(l(C)(D)) with a
property P* such that
1. V-i is a quasi-transitive V i -class for every i in {1, ..., k,
2. either D[{a is an element of A(D) : c(a) is an element of V-i]
is a subdigraph of D-1 or it is a sudigraph of D2 for every i in {1,
..., k,
3. D-i has no infinite outward path for every i in {1, 2,
4. every cycle of length three in D has at most two obstructions, then D
has an H-kernel.
Some results with respect to the existence of kernels by monochromatic
paths in finite digraphs will be deduced from the main result.
Filiaciones:
Manuel Campero-Alonzo, Jose:
Univ Nacl Autonoma Mexico, Fac Ciencias, Circuit Exterior S-N,Ciudad Univ, Ciudad De Mexico 04510, Cdmx, Mexico
Sanchez-Lopez, Rocio:
Univ Nacl Autonoma Mexico, Fac Ciencias, Circuit Exterior S-N,Ciudad Univ, Ciudad De Mexico 04510, Cdmx, Mexico
|