Some relations between neighbourhood graphs for a permutation problem

Many discrete optimization problems belong to the class NP-hard. Therefore heuristics have been developed for such problems. As regards iteration methods, the determination of a suitable neighbourhood plays an important role. This paper derives structural relations between different neighbourhood graphs where the set of solutions is characterized by the set of permutations of the integers 1,...,m. For two neighbours in a graph G1, it calculates the mean shortest length in some other graph G2. The paper also derives the maximum difference of shortest lengths in G2 and G1 between vertices which are connected in G1.