- Tytuł:
- Independent Detour Transversals in 3-Deficient Digraphs
- Autorzy:
-
van Aardt, Susan
Frick, Marietjie
Singleton, Joy - Powiązania:
- https://bibliotekanauki.pl/articles/30146646.pdf
- Data publikacji:
- 2013-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
longest path
independent set
detour transversal
strong digraph
oriented graph - Opis:
- 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 is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 261-275
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł