### Abstract

Let α be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of α in G by δ_{α}(G) = ∑x,y∈ V(G) |d_{G}(x,y)-d_{G}(α(x), α(y))|, where d_{G}(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 O(n^{5} log n) time, where n is the total number of vertices in a complete multipartite graph.

Original language | English |
---|---|

Pages (from-to) | 545-556 |

Number of pages | 12 |

Journal | Journal of Optimization Theory and Applications |

Volume | 110 |

Issue number | 3 |

DOIs | |

State | Published - 1 Sep 2001 |

### Keywords

- Chaotic mapping
- Complete multipartite graph
- Optimal solution
- Quadratic integer programming

## Fingerprint Dive into the research topics of 'Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs'. Together they form a unique fingerprint.

## Cite this

*Journal of Optimization Theory and Applications*,

*110*(3), 545-556. https://doi.org/10.1023/A:1017584227417