Displaying similar documents to “Kernels by monochromatic paths and the color-class digraph”

Kernels in monochromatic path digraphs

Hortensia Galeana-Sánchez, Laura Pastrana Ramírez, Hugo Alberto Rincón Mejía (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈...

Kernels and cycles' subdivisions in arc-colored tournaments

Pietra Delgado-Escalante, Hortensia Galeana-Sánchez (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there...

Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured...

Kernels in edge coloured line digraph

H. Galeana-Sánchez, L. Pastrana Ramírez (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed path between them and (ii) for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an...

Monochromatic paths and monochromatic sets of arcs in bipartite tournaments

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours and all of them are used. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices there is no monochromatic path between them and for every vertex v in V(D)∖N there is a monochromatic path from v to some vertex in N. We denote by A⁺(u) the set of arcs of D that have u as...

Kernels by Monochromatic Paths and Color-Perfect Digraphs

Hortensia Galeana-Śanchez, Rocío Sánchez-López (2016)

Discussiones Mathematicae Graph Theory

Similarity:

For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different...

On monochromatic paths and bicolored subdigraphs in arc-colored tournaments

Pietra Delgado-Escalante, Hortensia Galeana-Sánchez (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...

γ-Cycles In Arc-Colored Digraphs

Hortensia Galeana-Sánchez, Guadalupe Gaytán-Gómez, Rocío Rojas-Monroy (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We call a digraph D an m-colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ⊆ V (D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, and for every...

Rainbow Connectivity of Cacti and of Some Infinite Digraphs

Jesús Alva-Samos, Juan José Montellano-Ballesteros (2017)

Discussiones Mathematicae Graph Theory

Similarity:

An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair {u, v} ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds...

γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs

Enrique Casas-Bautista, Hortensia Galeana-Sánchez, Rocío Rojas-Monroy (2013)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A γ-cycle in D is a sequence of vertices, say γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ 0, 1, . . . , n there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the...

A note on kernels and solutions in digraphs

Matúš Harminc, Roman Soták (1999)

Discussiones Mathematicae Graph Theory

Similarity:

For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.

k-Kernels and some operations in digraphs

Hortensia Galeana-Sanchez, Laura Pastrana (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph. V(D) denotes the set of vertices of D; a set N ⊆ V(D) is said to be a k-kernel of D if it satisfies the following two conditions: for every pair of different vertices u,v ∈ N it holds that every directed path between them has length at least k and for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an xy-directed path of length at most k-1. In this paper, we consider some operations on digraphs and prove the existence of k-kernels in digraphs formed...

On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic...

Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. We call the digraph D an m-coloured digraph if each arc of D is coloured by an element of {1,2,...,m} where m ≥ 1. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if there is no monochromatic path between two vertices of N and if for every vertex v not in N there is a monochromatic path from v...

The k-Rainbow Bondage Number of a Digraph

Jafar Amjadi, Negar Mohammadi, Seyed Mahmoud Sheikholeslami, Lutz Volkmann (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight...