Source author record

Hortensia Galeana-Sánchez

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A dichotomy for the kernel by $H$ -walks problem in digraphs

Let $H = (V_H, A_H)$ be a digraph which may contain loops, and let $D = (V_D, A_D)$ be a loopless digraph with a coloring of its arcs $c: A_D \to V_H$ . An $H$ -walk of $D$ is a walk $(v_0, \dots, v_n)$ of $D$ such that $(c(v_{i-1}, v_i), c(v_i, v_{i+1}))$ is an arc of $H$ , for every $1 \le i \le n-1$ . For $u, v \in V_D$ , we say that $u$ reaches $v$ by $H$ -walks if there exists an $H$ -walk from $u$ to $v$ in $D$ . A subset $S \subseteq V_D$ is a kernel by $H$ -walks of $D$ if every vertex in $V_D \setminus S$ reaches by $H$ -walks some vertex in $S$ , and no vertex in $S$ can reach another vertex in $S$ by $H$ -walks. A panchromatic pattern is a digraph $H$ such that every arc-colored digraph $D$ has a kernel by $H$ -walks. In this work, we prove that every digraph $H$ is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph $D$ has a kernel by $H$ -walks is $NP$ -complete.

preprint2016arXiv

About $(k,l)$ -kernels, semikernels and Grundy functions in partial line digraphs

Let $D=(V,A)$ be a digraph and consider an arc subset $A'\subseteq A$ and an exhaustive mapping $ϕ: A\to A'$ such that $(i)$ the set of heads of $A'$ is $H(A')=V$ ; $(ii)$ the map fixes the elements of $A'$ , that is, $ϕ|A'=Id$ , and for every vertex $j\in V$ , $ϕ(ω^-(j))\subset ω^-(j)\cap A'$ . Then, {\it the partial line digraph} of $D$ , denoted by $\mathcal{L}_{(A',ϕ)}D$ (for short $\mathcal{L}D$ if the pair $(A', ϕ)$ is clear from the context), is the digraph with vertex set $V (\mathcal{L}D)=A'$ and set of arcs $A(\mathcal{L}D) = \{(ij, ϕ(j,k)) : (j,k)\in A\}.$ In this paper we prove the following results: Let $k,l$ be two natural numbers such that $1\le l \le k$ , and $D$ a digraph with minimum in-degree at least 1. Then the number of $(k,l)$ -kernels of $D$ is less than or equal to the number of $(k,l)$ -kernels of $\mathcal{L} D$ . Moreover, if $l<k$ and the girth of $D$ is at least $l+1$ , then these two numbers are equal. The number of semikernels of $D$ is equal to the number of semikernels of $\mathcal{L} D$ . Also we introduce the concept of $(k,l)$ -Grundy function as a generalization of the concept of Grundy function and we prove that the number of $(k,l)$ -Grundy functions of $D$ is equal to the number of $(k,l)$ -Grundy functions of any partial line digraph $\mathcal{L} D$ .

preprint2012arXiv

$k$ -colored kernels in semicomplete multipartite digraphs

An $m$ -colored digraph $D$ has $k$ -colored kernel if there exists a subset $K$ of its vertices such that for every vertex $v\notin K$ there exists an at most $k$ -colored directed path from $v$ to a vertex of $K$ and for every $% u,v\in K$ there does not exist an at most $k$ -colored directed path between them. In this paper we prove that an $m$ -colored semicomplete $r$ -partite digraph $D$ has a $k$ -colored kernel provided that $r\geq 3$ and {enumerate} [(i)] $k\geq 4,$ [(ii)] $k=3$ and every $\overrightarrow{C}_{4}$ contained in $D$ is at most 2-colored and, either every $\overrightarrow{C}_{5}$ contained in $D$ is at most 3-colored or every $\overrightarrow{C}_{3}\uparrow \overrightarrow{C}_{3}$ contained in $D$ is at most 2-colored, [(iii)] $k=2$ and every $\overrightarrow{C}_{3}$ and $\overrightarrow{C}%_{4}$ contained in $D$ is monochromatic. {enumerate} If $D$ is an $m$ -colored semicomplete bipartite digraph and $k=2$ (resp. $k=3$ ) and every $\overrightarrow{C}_{4}\upuparrows \overrightarrow{C}_{4}$ contained in $D$ is at most 2-colored (resp. 3-colored), then $D$ has a $% 2$ -colored (resp. 3-colored) kernel. Using these and previous results, we obtain conditions for the existence of $k$ -colored kernels in $m$ -colored semicomplete $r$ -partite digraphs for every $k\geq 2$ and $r\geq 2$ .

preprint2012arXiv

k-colored kernels

We study $k$ -colored kernels in $m$ -colored digraphs. An $m$ -colored digraph $D$ has $k$ -colored kernel if there exists a subset $K$ of its vertices such that (i) from every vertex $v\notin K$ there exists an at most $k$ -colored directed path from $v$ to a vertex of $K$ and (ii) for every $u,v\in K$ there does not exist an at most $k$ -colored directed path between them. In this paper, we prove that for every integer $k\geq 2$ there exists a $% (k+1)$ -colored digraph $D$ without $k$ -colored kernel and if every directed cycle of an $m$ -colored digraph is monochromatic, then it has a $k$ -colored kernel for every positive integer $k.$ We obtain the following results for some generalizations of tournaments: (i) $m$ -colored quasi-transitive and 3-quasi-transitive digraphs have a $k$ % -colored kernel for every $k\geq 3$ and $k\geq 4,$ respectively (we conjecture that every $m$ -colored $l$ -quasi-transitive digraph has a $k$ % -colored kernel for every $k\geq l+1)$ , and (ii) $m$ -colored locally in-tournament (out-tournament, respectively) digraphs have a $k$ -colored kernel provided that every arc belongs to a directed cycle and every directed cycle is at most $k$ -colored.

preprint2012arXiv

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs

Let $D=(V(D), A(D))$ be a digraph and $k \ge 2$ an integer. We say that $D$ is $k$ -quasi-transitive if for every directed path $(v_0, v_1,..., v_k)$ in $D$ , then $(v_0, v_k) \in A(D)$ or $(v_k, v_0) \in A(D)$ . Clearly, a 2-quasi-transitive digraph is a quasi-transitive digraph in the usual sense. Bang-Jensen and Gutin proved that a quasi-transitive digraph $D$ has a 3-king if and only if $D$ has a unique initial strong component and, if $D$ has a 3-king and the unique initial strong component of $D$ has at least three vertices, then $D$ has at least three 3-kings. In this paper we prove the following generalization: A $k$ -quasi-transitive digraph $D$ has a $(k+1)$ -king if and only if $D$ has a unique initial strong component, and if $D$ has a $(k+1)$ -king then, either all the vertices of the unique initial strong components are $(k+1)$ -kings or the number of $(k+1)$ -kings in $D$ is at least $(k+2)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Hortensia Galeana-Sánchez

Research overview

Is this your work?

5 publications

A dichotomy for the kernel by $H$ -walks problem in digraphs

About $(k,l)$ -kernels, semikernels and Grundy functions in partial line digraphs

$k$ -colored kernels in semicomplete multipartite digraphs

k-colored kernels

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs

See the researcher in context

Building this map preview

Hortensia Galeana-Sánchez

Research overview

Is this your work?

5 publications

A dichotomy for the kernel by HHH-walks problem in digraphs

About (k,l)(k,l)(k,l)-kernels, semikernels and Grundy functions in partial line digraphs

kkk-colored kernels in semicomplete multipartite digraphs

k-colored kernels

On the existence and number of (k+1)(k+1)(k+1)-kings in kkk-quasi-transitive digraphs

See the researcher in context

Building this map preview

A dichotomy for the kernel by $H$ -walks problem in digraphs

About $(k,l)$ -kernels, semikernels and Grundy functions in partial line digraphs

$k$ -colored kernels in semicomplete multipartite digraphs

On the existence and number of $(k+1)$ -kings in $k$ -quasi-transitive digraphs