Characterizations of k-traceable graphs and oriented graphs - Van Aardt, Susan A.; Prick, Marietjie; Dunbar, Jean E.; Nielsen, Morten H; Oellermann, Ortrud R. (Utilitas Mathematica, 2013)
A(di)graph G is k-traceable(k ≥ 2) if every induced sub(di)graph of G that has order k is traceable. In particular,a 2-traceable graph is complete and a 2-traceable oriented graph is a tournament. In this paper we give structural characterizations of k-traceable graphs for each k ≤ 6. We also characterize,for k ≤ 4, those graphs that have a k-traceable orientation.