A Study on the Chaotic Numbers of Graphs

Abstract

Given a sequence \(X = (x_1, x_2, \ldots, x_k)\), let \(Y = (y_1, y_2, \ldots, y_k)\) be a sequence obtained by rearranging the terms of \(X\). The total self-variation of \(Y\) relative to \(X\) is \(\zeta_X(Y) = \sum_{i=1}^k |y_i – x_i|\). On the other hand, let \(G = (V, E)\) be a connected graph and \(\phi\) be a permutation of \(V\). The total relative displacement of \(\phi\) is \(\delta_\phi(G) = \sum_{\{x \neq y\}\subset V} |d(x, y) – d(\phi(x), \phi(y))|\), where \(d(v, w)\) means the distance between \(v\) and \(w\) in \(G\). It’s clear that the total relative displacement of \(\phi\) is a total self-variation relative to the distance sequence of the graph.
In this paper, we determine the sequences which attain the maximum value of the total self-variation of all possible rearrangements \(Y\) relative to \(X\). Applying this result to the distance sequence of a graph, we find a best possible upper bound for the total relative displacement of a graph.