Three value TSP and linkages with the three value linear spanning 2-forests

We provide a polynomially testable characterization of cost matrices associated with the complete directed graph where all disjoint spanning 2-paths (linear spanning 2-forests) have exactly one, two or three distinct values. Using this result, we identify a class of cost matrices where the number of distinct values of Hamiltonian cycles (paths) in a complete digraph is three. A complete characterization of general cost matrices with the property that all associated Hamiltonian cycles have at most kk distinct values is an open question for k≥3k≥3.

► New sufficient conditions for three value TSP cost matrices. ► Complete characterization of one, two, and three value linear spanning 2-forests cost matrices. ► New TSP solvable cases.