Independent Detour Transversals in 3-Deficient Digraphs
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 inters...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1650 |
| _version_ | 1827840307195019264 |
|---|---|
| author | van Aardt Susan Frick Marietjie Singleton Joy |
| author_facet | van Aardt Susan Frick Marietjie Singleton Joy |
| author_sort | van Aardt Susan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T07:32:49Z |
| format | Article |
| id | doaj.art-0934042e921a45d580223d149b0e596f |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:49Z |
| publishDate | 2013-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-0934042e921a45d580223d149b0e596f2023-09-02T21:42:47ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-05-0133226127510.7151/dmgt.1650Independent Detour Transversals in 3-Deficient Digraphsvan Aardt Susan0Frick Marietjie1Singleton Joy2Department of Mathematical Sciences University of South Africa P.O. Box 392, Unisa, 0003, South AfricaDepartment of Mathematical Sciences University of South Africa P.O. Box 392, Unisa, 0003, South AfricaDepartment of Mathematical Sciences University of South Africa P.O. Box 392, Unisa, 0003, South AfricaIn 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.https://doi.org/10.7151/dmgt.1650longest pathindependent setdetour transversalstrong digraphoriented graph |
| spellingShingle | van Aardt Susan Frick Marietjie Singleton Joy Independent Detour Transversals in 3-Deficient Digraphs Discussiones Mathematicae Graph Theory longest path independent set detour transversal strong digraph oriented graph |
| title | Independent Detour Transversals in 3-Deficient Digraphs |
| title_full | Independent Detour Transversals in 3-Deficient Digraphs |
| title_fullStr | Independent Detour Transversals in 3-Deficient Digraphs |
| title_full_unstemmed | Independent Detour Transversals in 3-Deficient Digraphs |
| title_short | Independent Detour Transversals in 3-Deficient Digraphs |
| title_sort | independent detour transversals in 3 deficient digraphs |
| topic | longest path independent set detour transversal strong digraph oriented graph |
| url | https://doi.org/10.7151/dmgt.1650 |
| work_keys_str_mv | AT vanaardtsusan independentdetourtransversalsin3deficientdigraphs AT frickmarietjie independentdetourtransversalsin3deficientdigraphs AT singletonjoy independentdetourtransversalsin3deficientdigraphs |