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](http://oeis.org/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). 



Energy of a graph
In the case of the $n$-cycle there will be two ways to write the optimal permutations. In the case when we write them like $$(1),(1,2),(1,2,3),(1,2,4,3),(1,2,4,5,3),(1,2,4,6,5,3),\dots$$ 
this will be the fractalization of the sequence $$1,2,3,3,4,4,5,5,6,6,\dots$$
Notice that the coincidence with the fractalization of $1+\lfloor n/\sqrt{5} \rfloor$ stops after $n=10$. For example the permutation $(1, 2, 4, 6, 8, 11, 10, 9, 7, 5, 3)$ which appears in A194983 is not optimal.


I would prefer to write the permutations with the opposite orientation, so that one gets
$$(1),(1,2),(1,3,2),(1,3,4,2),(1,3,5,4,2),\dots$$ 
which is the [fractalization of $1+\lfloor n/2\rfloor$](http://oeis.org/A194959). 


This is of course just a fancy way of saying that the optimal permutations contain the two largest entries in consecutive positions and can be generated recursively by inserting $n+1$ between $n$ and $n-1$. This can be proven easily by induction.


Proof: Let C(n) be the value of $\sum \pi(i)\pi(i+1)$ (cyclic sum) for these permutations. We have $C(n)=C(n-1)+n^2-2$. Suppose the statement is true for $n-1$. Now let $\sigma\in S\_n$ be a random permutation. We will prove that $\sum \sigma(i)\sigma(i+1)\le C(n)$. But $\sum \sigma(i)\sigma(i+1)=n(a+b)-ab+\sum \sigma'(i)\sigma'(i+1)\le C(n-1)+n(a+b)-ab$
where $\sigma'\in S\_{n-1}$ is obtained from sigma by deleting $n$, so we just need to show 
$$C(n-1)+n(a+b)-ab\le C(n)$$ which can be written as $(n-a)(n-b)\geq 2$, so we are done. 


For the general problem, this is close to the problem of minimizing the $\lambda$-cost over all labelings $\pi$. Where the cost of an edge is $|\pi(i)-\pi(j)|^\lambda$. In fact for regular graphs your problem is equivalent to minimizing the cost for $\lambda=2$. Unfortunately, I don't think much is known about this beyond $\lambda=1$.


