On k-anti-traceability of oriented graphs
Bin Chen, Stefanie Gerke, Gregory Gutin, Hui Lei, Heis Parker-Cox, Yacong Zhou · Discrete Mathematics · 2024
An oriented path P is called anti-directed if every two consecutive arcs of P have opposite orientations. An oriented graph is called k -anti-traceable if every subdigraph induced by k vertices has a hamiltonian anti-directed path. We introduce and study a conjecture, which claims that for every integer k ≥ 2 there is a least integer f ( k ) such that each k -anti-traceable oriented graph on f ( k ) vertices has a hamiltonian anti-directed path. We determine f ( 2 ) , f ( 3 ) , f ( 4 ) and show that every k -anti-traceable oriented graph on sufficiently large number n of vertices admits an anti-directed path that contains all but o ( n ) vertices.