Let $D=(V,A)$ be an acyclic digraph. For $xin V$ define $e_{_{D}}(x)$ to be the difference of the indegree and the outdegree of $x$. An acyclic ordering of the vertices of $D$ is a one-to-one map $g: V rightarrow [1,|V|] $ that has the property that for all $x,yin V$ if $(x,y)in A$, then $g(x) < g(y)$. We prove that for every acyclic ordering $g$ of $D$ the following inequality holds: [sum_{xin V} e_{_{D}}(x)cdot g(x) ~geq~ frac{1}{2} sum_{xin V}[e_{_{D}}(x)]^2~.] The class of acyclic digraphs for which equality holds is determined as the class of comparbility digraphs of posets of order dimension two.
تحميل البحث