Displaying similar documents to “Isomorphisms and traversability of directed path graphs”

Independent Detour Transversals in 3-Deficient Digraphs

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

On independent sets and non-augmentable paths in directed graphs

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