My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) < \eta(v) $. Therefore, the directed graph obtained is a directed acyclic graph (DAG).
In this directed graph, is it true that the minimum over all orderings of $ \sum _{i \in V} d^+(i)d^+(i) $ is greater or equal to the minimum over all orderings of $ \sum _{i \in V} d^+(i)d^-(i)$? ($d^+(i)$ is the out-degree of $i$ and $d^-(i)$ is its in-degree)
My impression is that it is. There is no obvious minimum ordering for $ \sum _{i \in V} d^+(i)d^-(i) $, as this problem is known to be NP-hard - see this question on Theoretical Computer Science. I don't know if it is the case for $ \sum _{i \in V} d^+(i)d^+(i) $. Maybe it is possible to prove that we can always find an ordering which makes $ \sum _{i \in V} d^+(i)d^-(i) $ smaller or equal to the minimum of $ \sum _{i \in V} d^+(i)d^+(i) $.
