Geodesic
Every 8-Traceable Oriented Graph Is Traceable
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 963-973 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.
Keywords: oriented graph, traceable, hypotraceable, k-traceable, generalized tournament 
@article{DMGT_2017_37_4_a7,
     author = {Aardt, Susan A. van},
     title = {Every {8-Traceable} {Oriented} {Graph} {Is} {Traceable}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {963--973},
     year = {2017},
     volume = {37},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a7/}
}
TY  - JOUR
AU  - Aardt, Susan A. van
TI  - Every 8-Traceable Oriented Graph Is Traceable
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 963
EP  - 973
VL  - 37
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a7/
LA  - en
ID  - DMGT_2017_37_4_a7
ER  - 
%0 Journal Article
%A Aardt, Susan A. van
%T Every 8-Traceable Oriented Graph Is Traceable
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 963-973
%V 37
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a7/
%G en
%F DMGT_2017_37_4_a7
Aardt, Susan A. van. Every 8-Traceable Oriented Graph Is Traceable. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 963-973. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a7/

[1] S.A. van Aardt, A.P. Burger, J.E. Dunbar, M. Frick, J.M. Harris and J.E. Singleton, An iterative approach to the Traceabiltiy Conjecture for Oriented Graphs, Electron. J. Combin. 201 (2013) #P59.

[2] S.A. van Aardt, A.P. Burger, M. Frick, B. Llano and R. Zuazua, Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs, Graphs Combin. 30 (2014) 783-800. doi: 0.1007/s00373-013-1312-1

[3] 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

[4] S.A. van Aardt, J.E. Dunbar, M. Frick and M.H. Nielsen, Cycles in k-traceable oriented graphs, Discrete Math. 311 (2011) 2085-2094. doi: 10.1016/j.disc.2011.05.032

[5] S.A. van Aardt, J.E. Dunbar, M. Frick, M.H. Nielsen and O.R. Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin. 15 (2008) #R150.

[6] S.A. van Aardt, M. Frick, P. Katrenič and M.H. Nielsen, The order of hypotraceable oriented graphs, Discrete Math. 11 (2011) 1273-1280. doi: 10.1016/j.disc.2011.03.009

[7] A.P. Burger, Computational results on the traceability of oriented graphs of small order, Electron. J. Combin. 20 (2013) #P23.

[8] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Ed. (Springer-Verlag, London, 2009). doi: 10.1007/978-1-84800-998-1

[9] M. Frick and P. Katrenič, Progress on the traceability conjecture, Discrete Math. Theor. Comput. Sci. 10 (2008) 105-114.

[10] M. Grötschel and Y. Wakabayashi, Constructions of hypotraceable digraphs, in: Mathematical Programming, R.W. Cottle, M.L. Kelmanson and B. Korte (Ed(s)), (Elsevier Science Publishers B.V., 1984).