Generalizations and extensions of the constant travelling salesman problem
Daniel K. Benvenuti · Summit (Simon Fraser University) · 2007
This thesis gives a characterization of cost matrices associated with the complete directed graph that have at most three distinct values for linear spanning 2-forests. Alternative characterizations of cost matrices where all Hamiltonian paths and Hamiltonian cycles have at most two distinct values are also given. The only known characterization for three values of Hamiltonian paths and cycles is for skew-symmetric matrices. Similar results are obtained with different restrictions on the structure of the cost matrix. Furthermore, this thesis identifies generalizations of the constant-TSP for arbitrary graphs whose associated cost matrix is well-structured. The SC-Hamiltonicity of various classes of undirected and directed graphs is determined. A complete characterization of SC-Hamiltonicity in terms of strong Hamiltonicity is given for undirected graphs. In addition, interesting classifications are found which contradict previous claims regarding SC-Hamiltonian graphs.