Some remarks about digraphs with nonisomorphic - or -neighbourhoods
Halina Bielak, Elżbieta Soczewińska (1983)
Časopis pro pěstování matematiky
Similarity:
Halina Bielak, Elżbieta Soczewińska (1983)
Časopis pro pěstování matematiky
Similarity:
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...
Pavel Komárek (1984)
Časopis pro pěstování matematiky
Similarity:
H. Galeana-Sánchez (1998)
Discussiones Mathematicae Graph Theory
Similarity:
We investigate sufficient conditions, and in case that D be an asymmetrical digraph a necessary and sufficient condition for a digraph to have the following property: "In any induced subdigraph H of D, every maximal independent set meets every non-augmentable path". Also we obtain a necessary and sufficient condition for any orientation of a graph G results a digraph with the above property. The property studied in this paper is an instance of the property of a conjecture of J.M. Laborde,...
Susan van Aardt, Marietjie Frick, Joy Singleton (2013)
Discussiones Mathematicae Graph Theory
Similarity:
In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph...
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 ∈...
Bhargava, T.N., O'Korn, L.J. (1967)
Portugaliae mathematica
Similarity:
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...