DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 261-275
DOI: https://doi.org/10.7151/dmgt.1650

Independent Detour Transversals in 3-deficient Digraphs

Susan van Aardt, Marietjie Frick
and
Joy Singleton

Department of Mathematical Sciences
University of South Africa
P.O. Box 392, Unisa, 0003, South Africa

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.

Keywords: longest path, independent set, detour transversal, strong digraph, oriented graph

2010 Mathematics Subject Classification: 05C20, 05C38.

References

[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.
[2]S.A. van Aardt, J.E. Dunbar, M. Frick, P. Katrenič, 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.
[3]J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2001).
[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.
[5]J.A. Bondy, Basic graph theory: Paths and circuits, in: Handbook of Combinatorics, ed(s), R.L. Graham, M. Grötschel and L. Lovász The MIT Press, Cambridge, MA, 1995) Vol I, p. 20.
[6]P. Camion, Chemins et circuits hamiltoniens des graphes complets, C.R. Acad. Sci. Paris 249 (1959) 2151--2152.
[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.
[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.
[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.
[10]F. Havet, Stable set meeting every longest path, Discrete Math. 289 (2004) 169--173, doi: 10.1016/j.disc.2004.07.013.
[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.

Received 19 October 2011
Revised 28 February 2012
Accepted 28 February 2012

Close