- Tytuł:
- H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs
- Autorzy:
-
Campero-Alonzo, José Manuel
Sánchez-López, Rocío - Powiązania:
- https://bibliotekanauki.pl/articles/32083861.pdf
- Data publikacji:
- 2021-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
quasi-transitive digraph
kernel by monochromatic paths
alternating kernel
obstruction
H-kernel - Opis:
- 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})) ∉ 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) \backslash N\) there exists an $H$-path in $D$ from $u$ to $N$. Let $D$ be an arc-colored digraph. The color-class digraph of $D,\mathcal{C}_C(D)$, is the digraph such that $V(\mathcal{C}_C(D)) = \{c(a) : a ∈ A(D)\}$ and $(i, j) ∈ A(\mathcal{C}_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 ∪ 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(\mathcal{C}_C(D))$ with a property $P^\ast$ such that 1. $V_i$ is a quasi-transitive $V_i$-class for every i in $\{1, . . ., k\}$, 2. either \(D[\{a ∈ A(D) : c(a) ∈ V_i\}]\) is a subdigraph of $D_1$ or it is a sudigraph of $D_2$ 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 391-408
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł