pith. sign in

arxiv: 1110.3107 · v2 · pith:QCYSA6JVnew · submitted 2011-10-14 · 🧮 math.CO

Some inequalities for orderings of acyclic digraphs

classification 🧮 math.CO
keywords acyclicdigraphsclassholdsorderingcdotcomparbilitydefine
0
0 comments X
read the original abstract

Let $D=(V,A)$ be an acyclic digraph. For $x\in 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,y\in 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_{x\in V} e_{_{D}}(x)\cdot g(x) ~\geq~ \frac{1}{2} \sum_{x\in 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.