Quadratic Integer Programming with Application to the Chaotic Mappings of Complete Multipartite Graphs

Let be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of in G by be where _{dG(x, y)} is the length of the shortest path between x and y in G. Let ^*(G) be the maximum value of (G) among all permutations of V(G). The permutation which realizes ^*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem is reduced to a quadratic integer programming problem. We characterize its optimal solution and present an algorithm running in time, where n is the total number of vertices in a complete multipartite graph.