# Independent Detour Transversals in 3-Deficient Digraphs

Susan van Aardt; Marietjie Frick; Joy Singleton

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 2, page 261-275
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSusan van Aardt, Marietjie Frick, and Joy Singleton. "Independent Detour Transversals in 3-Deficient Digraphs." Discussiones Mathematicae Graph Theory 33.2 (2013): 261-275. <http://eudml.org/doc/268060>.

@article{SusanvanAardt2013,

abstract = {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.},

author = {Susan van Aardt, Marietjie Frick, Joy Singleton},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {longest path; independent set; detour transversal; strong digraph; oriented graph},

language = {eng},

number = {2},

pages = {261-275},

title = {Independent Detour Transversals in 3-Deficient Digraphs},

url = {http://eudml.org/doc/268060},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Susan van Aardt

AU - Marietjie Frick

AU - Joy Singleton

TI - Independent Detour Transversals in 3-Deficient Digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 2

SP - 261

EP - 275

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

LA - eng

KW - longest path; independent set; detour transversal; strong digraph; oriented graph

UR - http://eudml.org/doc/268060

ER -

## References

top- [1] S.A. van Aardt, G. Dlamini, J. Dunbar, M. Frick, and O. Oellermann, The directed path partition conjecture, Discuss. Math. Graph Theory 25 (2005) 331-343. doi:10.7151/dmgt.1286[Crossref] Zbl1118.05040
- [2] S.A. van Aardt, J.E. Dunbar, M. Frick, P. Katreniˇc, M.H. Nielsen, and O.R. Oellermann, Traceability of k-traceable oriented graphs, Discrete Math. 310 (2010) 1325-1333. doi:10.1016/j.disc.2009.12.022[WoS][Crossref] Zbl1195.05030
- [3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2001). Zbl0958.05002
- [4] J. Bang-Jensen, M.H. Nielsen and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306 (2006) 1830-1839. doi:10.1016/j.disc.2006.03.063[Crossref] Zbl1103.05036
- [5] J.A. Bondy, Basic graph theory: Paths and circuits, in: Handbook of Combinatorics, R.L. Graham, M. Gr¨otschel and L. Lov´asz (Ed(s)), (The MIT Press, Cambridge, MA, 1995) Vol I, p. 20. Zbl0849.05044
- [6] P. Camion, Chemins et circuits hamiltoniens des graphes complets, C.R. Acad. Sci. Paris 249 (1959) 2151-2152. Zbl0092.15801
- [7] C.C. Chen and P. Manalastas Jr., Every finite strongly connected digraph of stability 2 has a Hamiltonian path, Discrete Math. 44 (1983) 243-250. doi:10.1016/0012-365X(83)90188-7 Zbl0507.05036
- [8] H. Galeana-Sánchez and R. Gómez, Independent sets and non-augmentable paths in generalizations of tournaments, Discrete Math. 308 (2008) 2460-2472. doi:10.1016/j.disc.2007.05.016[Crossref][WoS] Zbl1147.05042
- [9] H. Galeana-Sánchez and H.A. Rincón-Mejía, Independent sets which meet all longest paths, Discrete Math. 152 (1996) 141-145. doi:10.1016/0012-365X(94)00261-G[Crossref]
- [10] F. Havet, Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173. doi:10.1016/j.disc.2004.07.013[Crossref] Zbl1056.05072
- [11] J.M. Laborde, C. Payan, N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983).
- [12] M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573-590. doi:10.2307/1969755[Crossref] Zbl0053.02902

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.