Displaying similar documents to “On independent sets and non-augmentable paths in directed graphs”

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

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

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