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

Abstract

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

How to cite

top

Susan 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. [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. [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. [3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2001). Zbl0958.05002
  4. [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. [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. [6] P. Camion, Chemins et circuits hamiltoniens des graphes complets, C.R. Acad. Sci. Paris 249 (1959) 2151-2152. Zbl0092.15801
  7. [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. [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. [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. [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. [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. [12] M. Richardson, Solutions of irreflexive relations, Ann. of Math. 58 (1953) 573-590. doi:10.2307/1969755[Crossref] Zbl0053.02902

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.