A Study on the Chaotic Numbers of Graphs

Abstract

Given a sequence $X=(x_1,x_2,\dots ,x_k)$, let $Y=(y_1,y_2,\dots ,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 $\varphi$ be a permutation of $V$. The total relative displacement of $\varphi$ is ${\delta }_{\varphi }(G)=\sum _{\{x\ne y\}\subset V}|d(x,y)–d(\varphi (x),\varphi (y))|$, where $d(v,w)$ means the distance between $v$ and $w$ in $G$. It’s clear that the total relative displacement of $\varphi$ 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.