DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

J.M. Campero-Alonzo, R. Sánchez-López

Title:

$H$-kernels in unions of $H$-colored quasi-transitive digraphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-03-14, Revised: 2018-11-06, Accepted: 2018-11-07, https://doi.org/10.7151/dmgt.2199

Abstract:

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,\ldots,v_n)$ in an $H$-colored digraph $D$ will be called $H$-path if and only if $(c(v_0,v_1),\ldots, 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}))\notin 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)\setminus 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$, $\mathscr{C}_C(D)$, is the digraph such that $V(\mathscr{C}_C(D))=\{c(a):a\in A(D)\}$ and $(i,j)\in A(\mathscr{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\cup D_2$ is an $H$-colored digraph which is a union of asymmetric quasi-transitive digraphs and $\{V_1,\ldots,V_k\}$ is a partition of $V(\mathscr{C}_C(D))$ with a property $P^*$ such that \begin{list}{\labelwidth=0.5cm\labelsep=0.2cm\itemsep3pt\parsep0pt \topsep0pt\leftmargin=0.7cm} \item[1.] $V_i$ is a quasi-transitive $V_i$-class for every $i$ in $\{1,\ldots,k\}$, \item[2.] {either} $D[\{a\in A(D):c(a)\in V_i\}]$ is a subdigraph of $D_1$ or it is a sudigraph of $D_2$ for every $i$ in $\{1,\ldots,k\},$ \item[3.] $D_i$ has no infinite outward path for every $i$ in $\{1, 2\},$ \item[4.] {every} cycle of length three in $D$ has at most two obstructions, \end{list} {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.

Keywords:

quasi-transitive digraph, kernel by monochromatic paths, alternating kernel, $H$-kernel, obstruction

PDF
Close