Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: detour transversal

Sortuj według:

Ogranicz wyniki do:

Independent Detour Transversals in 3-Deficient Digraphs

100%

van Aardt S., Frick M., Singleton J.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

261-275

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Frick M.

1 Singleton J.

1 van Aardt S.

1 2013

Wyniki wyszukiwania

Independent Detour Transversals in 3-Deficient Digraphs