Let $G=(V,E)$ be a finite graph with weights $\phi: V\to \{1,...,|V|\}$ assigned to vertices. We can view $V$ as the set of numbers $1,...,|V|$, and $\phi$ as a permutation of $V$. For every edge $e$ we assign its energy $\phi(e_-)*\phi(e_+)$ (the product of weights of its end vertices). The energy of $\phi$ is the sum of energies of all edges from $E$. We are interested in $\phi$ that maximizes the energy of $G$. Is anything known about this problem?

For example, if $G$ is an $n$-cycle, $1-2-...-n-1$, then for $n=3$ all $\phi$'s have the same energy. If $n=4$, then the maximal energy is given by $\phi=(1,2,4,3)$, for $n=5$, we get $\phi=(1,2,4,5,3)$, for $n=6$, $\phi=(1,2,4,6,5,3)$, etc. (the new number gets inserted between two biggest numbers in the previous permutation. The interesting thing is that the sequence $1,2,3, 1,2,4,5,3, 1,2,3,4,6,5,3,...$ seems to coincide with A194983 which is defined in OEIS in a completely different way. I can prove it for $n\le 10$. Is it possible to prove the coincidence for all $n$?

** Update. ** Gjergji answered the question about the cycle. See comments below about other interesting graphs, other collections of weights and the problem of minimalizing the energy (maximizing the cost).