The chaotic numbers of the bipartite and tripartite graphs

Let G = (V, E) be a connected graph and let phi be a permutation of V. The total relative displacement of the permutation phi of G is delta phi(G) = Sigma({x,y}subset of V) vertical bar d(x,y)-d(phi(x),phi(y))vertical bar, where d(x, y) means the distance between x and y in G. The maximum value of delta(phi)(G) among all permutations in a graph G is called the chaotic number of G and the permutation which attains to the chaotic number is called a chaotic mapping of G. In this paper, we study the chaotic number of bipartite and tripartite graphs and find the closed form formulas for the bipartite graphs and an algorithm running in O(n(3)(4)) time to find the chaotic numbers of tripartite graphs where n(3) is the number of vertices in the biggest partite set. We emphasize that it partially improves an algorithm proposed in [5].