# Searching for name of equivalence property in hamiltonian paths

This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.

Given a hamiltonian path, any subpath will consist of a start, end, and set of interior vertices. Any ordering of the interior vertices will possibly yield a path existing within the graph, that when substituted for the original will yield another valid hamiltonian path. These subpaths would therefore form an equivalence class.

Under this relation, two paths would be equivalent if they have the same start vertex, the same end vertex, and the same set of interior vertices.

Does this equivalence class have a name? If so, are there any TSP optimization algorithms that make use of this?

• @user3266: Sorry if this is obvious, but how do one permute the order of the interior vertices and construct another valid Hamiltonian path? Or, only if such property exists then you put it into the equivalence class? Jan 16 '11 at 2:52
• I believe OP means to permute the end nodes? Jan 16 '11 at 3:03
• There's a well-known randomized algorithm that uses pivoting, which is similar to this observation. The observation in general, though, is false (if I understand it correctly!): consider a circle. Jan 16 '11 at 3:06
• I am not sure if you are really referring to an equivalence class at all. Jan 16 '11 at 4:58
• The set of all pairs of vertices that admit a Hamiltonian path? Jan 16 '11 at 6:08