The traveling salesman problem in graphs with some excluded minors (Q1184343): Difference between revisions

Let \(G=(V,E)\) be a finite, loopless, undirected graph with vertex set \(V\) and edge set \(E\) having non-negative edge weights. A tour \(T\) of \(G\) is a closed walk that passes through each vertex of \(G\). The length of \(T\) is the sum of the lengths of the edges in \(T\). The Graphical Traveling Salesman Problem is that of finding a tour in \(G\) of minimum length. The authors characterize those graphs for which the convex hull of all solutions is given by the non-negativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given.