Isomorphisms and traversability of directed path graphs

Hajo Broersma; Xueliang Li

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

Some new good characterizations for directed graphs

Pavel Komárek (1984)

Časopis pro pěstování matematiky

Similarity:

Nearly acyclic digraphs

Bohdan Zelinka (1983)

Czechoslovak Mathematical Journal

Similarity:

Antipodal graphs and digraphs.

Johns, Garry, Sleno, Karen (1993)

International Journal of Mathematics and Mathematical Sciences

Similarity:

The signed k-domination number of directed graphs

Maryam Atapour, Seyyed Sheikholeslami, Rana Hajypory, Lutz Volkmann (2010)

Open Mathematics

Similarity:

A traceability conjecture for oriented graphs.

Frick, Marietjie, van Aardt, Susan A., Dunbar, Jean E., Nielsen, Morten H., Oellermann, Ortrud R. (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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