A Linear Bound for the Traceability Conjecture

Nicolas Lichiardopol
Lycée Craponne, Salon, France

Susan van Aardt
University of South Africa

Jean. E Dunbar
Converse College, USA

Marietjie Frick
University of South Africa



Content: An oriented graph $D$ is said to be traceable if it admits a hamiltonian path. For $k\geq 2$, an oriented graph $D$ of order at least $k$, is said to be $k$-traceable if any subset of $k$ vertices of $D$ induces a traceable oriented graph. We denote by $t(k)$ the smallest integer bigger than or equal to $k$ such that every $k$-traceable oriented graph of order at least $t(k)$ is traceable. The Traceability Conjecture states that $t(k)\leq 2k-1$ for every $k\geq 2$. (see [3]). It was proved in [2], [1] and [4] that $t(k)=k$ for $2\leq k\leq 6$, $t(7)=9$, $t(8)\leq 14$ and that $t(k)\leq 2k^2-20k+59$ for $k\geq 9$ (which is a quadratic upper bound on $t(k)$). In this paper we prove that for $k\geq 4$, any $k$-traceable orgraph of order $n\geq 6k-20$ is traceable. This is the first linear bound in the story of the Traceability Conjecture. %---------------------------------------------------------------- \vspace{5mm} \noindent{\bf References: } \begin{itemize} \item[{[1]}] S.A. van Aardt, A.P. Burger, J.E. Dunbar, M. Frick, J.M. Harris, J.E. Singleton, An iterative approach to the traceabilty conjecture for oriented Graphs, Electronic J. Combin. 20(1): P59, (2013). \item[{[2]}] S.A van Aardt, J. E. Dunbar, M. Frick, P. Katreni\u{c}, M. H. Nielsen, O. R. Oellermann, Traceability of $k$-traceable oriented graphs, \item[{[3]}] S.A van Aardt, J. E. Dunbar, M. Frick, M. H. Nielsen, O. R. Oellermann, A traceability conjecture for oriented graphs, Electronic. J. Combin 15(1)R150(2008). \item[{[4]}] A.P. Burger, Computational results on the traceability of oriented graphs of small order, Electronic J. Combin. 20(4): P23, (2013). \end{itemize}

Back to all abstracts