Displaying similar documents to “The k-Rainbow Bondage Number of a Digraph”

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 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...

Signed Total Roman Domination in Digraphs

Lutz Volkmann (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Let D be a finite and simple digraph with vertex set V (D). A signed total Roman dominating function (STRDF) on a digraph D is a function f : V (D) → {−1, 1, 2} satisfying the conditions that (i) ∑x∈N−(v) f(x) ≥ 1 for each v ∈ V (D), where N−(v) consists of all vertices of D from which arcs go into v, and (ii) every vertex u for which f(u) = −1 has an inner neighbor v for which f(v) = 2. The weight of an STRDF f is w(f) = ∑v∈V (D) f(v). The signed total Roman domination number γstR(D)...

Kernels by monochromatic paths and the color-class digraph

Hortensia Galeana-Sánchez (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An m-colored digraph is a digraph whose arcs are colored with m colors. A directed path is monochromatic when its arcs are colored alike. A set S ⊆ V(D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x,y ∈ S, x ≠ y, there is no monochromatic directed path between them. 2. For each z ∈ (V(D)-S) there exists a zS-monochromatic directed path. In this paper it is introduced the concept of...

γ-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...

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...

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...

Dichromatic number, circulant tournaments and Zykov sums of digraphs

Víctor Neumann-Lara (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic...

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...

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 ∈...

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...

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...