×

Traceability of \(k\)-traceable oriented graphs. (English) Zbl 1195.05030

Summary: A digraph of order at least \(k\) is \(k\)-traceable if each of its subdigraphs of order \(k\) is traceable. We note that 2-traceable oriented graphs are tournaments and for \(k\geq 3, k\)-traceable oriented graphs can be regarded as generalized tournaments. We show that for \(2\leq k\leq 6\) every \(k\)-traceable oriented graph is traceable, thus extending the well-known fact that every tournament is traceable. This result does not extend to \(k=7\). In fact, for every \(k\geq 7\), except possibly for \(k=8\) or 10, there exist \(k\)-traceable oriented graphs that are nontraceable. However, we show that for every \(k\geq 2\) there exists a smallest integer \(t(k)\) such that every \(k\)-traceable oriented graph of order at least \(t(k)\) is traceable.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Nielsen, M. H.; Yeo, A., Longest path partitions in generalizations of tournaments, Discrete Math., 306, 1830-1839 (2006) · Zbl 1103.05036
[2] Chen, C. C.; Manalastas, P., Every finite strongly connected digraph of stability 2 has a Hamiltonian path, Discrete Math., 44, 243-250 (1983) · Zbl 0507.05036
[3] Frick, M.; Katrenič, P., Progress on the traceability conjecture, Discrete Math. and Theor. Comp. Science, 10, 3, 105-114 (2008) · Zbl 1196.05036
[4] Galeana-Sánchez, H.; Gómez, R., Independent sets and nonaugmentable paths in generalizations of tournaments, Discrete Math., 308, 12, 2460-2472 (2008) · Zbl 1147.05042
[5] Galeana-Sánchez, H.; Rincón-Mejia, H. A., Independent sets which meet all longest paths, Discrete Math., 152, 141-145 (1996) · Zbl 0856.05045
[6] Grötschel, M.; Thomassen, C.; Wakabayashi, Y., Hypotraceable digraphs, J. Graph Theory, 4, 377-381 (1980) · Zbl 0453.05030
[7] Havet, F., Stable set meeting every longest path, Discrete Math., 289, 169-173 (2004) · Zbl 1056.05072
[8] Laborde, J. M.; Payan, C.; Xuong, N. H., Independent sets and longest directed paths in digraphs, (Graphs and Other Combinatorial Topics (Prague, 1982). Graphs and Other Combinatorial Topics (Prague, 1982), Teubner-Texte Math., vol. 59 (1983)), 173-177 · Zbl 0528.05034
[9] van Aardt, S. A.; Dlamini, G.; Dunbar, J. E.; Frick, M.; Oellermann, O. R., The directed path partition conjecture, Discuss. Math. Graph Theory, 25, 331-343 (2005) · Zbl 1118.05040
[10] van Aardt, S. A.; Dunbar, J. E.; Frick, M.; Nielsen, M. H.; Oellermann, O. R., A traceability conjecture for oriented graphs, Electron. J. Combin., 15, 1, R150 (2008) · Zbl 1178.05046
[11] S.A. van Aardt, M. Frick, P. Katrenič, M.H. Nielsen, The order of hypotraceable oriented graphs (submitted for publication); S.A. van Aardt, M. Frick, P. Katrenič, M.H. Nielsen, The order of hypotraceable oriented graphs (submitted for publication)
[12] S.A. van Aardt, M. Frick, C.A. Whitehead, Significant differences between path partitions in directed and undirected graphs, Utilitas Math. (in press); S.A. van Aardt, M. Frick, C.A. Whitehead, Significant differences between path partitions in directed and undirected graphs, Utilitas Math. (in press) · Zbl 1242.05141
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.