An Introduction to Maximum Sum Permutations of Graphs

Abstract

This paper introduces the problem of finding a permutation \(\phi\) on the vertex set \(V(G)\) of a graph \(G\) such that the sum of the distances from each vertex to its image under \(\phi\) is maximized. We let \(\mathcal{S}(G) = \max \sum_{v\in V(G)} d(v, \phi(v))\), where the maximum is taken over all permutations \(\phi\) of \(V(G)\). Explicit formulae for several classes of graphs as well as general bounds are presented.