Characterizations of k-Traceable Graphs and Oriented Graphs

摘要

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.