An Iterative Approach to the Traceability Conjecture for Oriented Graphs

  • Susan van Aardt
  • Alewyn Burger
  • Jean Dunbar
  • Marietjie Frick
  • John Harris
  • Joy Singleton
Keywords: Traceability Conjecture, Path Partition Conjecture, oriented graph, generalized tournament, traceable, $k$-traceable, longest path.

Abstract

A digraph is $k$-traceable if its order is at least $k$ and each of its subdigraphs of order $k$ is traceable.  The Traceability Conjecture (TC) states that for $k\geq 2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. It has been shown that for $2\leq k\leq 6$, every $k$-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every $7$-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.

Author Biographies

Susan van Aardt, University of South Africa
Deartment of Mathematical Sciences, Professor
Alewyn Burger, University of Stellenbosch
Department of Logistics
Marietjie Frick, University of South Africa
Department of Mathematical Sciences, Research Fellow
Joy Singleton, University of South Africa
Department of Mathematical Sciences
Published
2013-03-24
Article Number
P59