×

Some inequalities for orderings of acyclic digraphs. (English) Zbl 1384.05089

Summary: 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 comparability digraphs of posets of order dimension two.

MSC:

05C20 Directed graphs (digraphs), tournaments
06A05 Total orders
06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite

References:

[1] K. A. Baker, P. C. Fishburn, and F. S. Roberts, Partial orders of dimension 2, Net works 2 (1972), 11-28. · Zbl 0247.06002
[2] J. Bang-Jensen and G. Gutin, Digraphs, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2001, Theory, algorithms and applications. · Zbl 0958.05002
[3] T. Bier, Some inequalities for linear extensions of posets and ideals, Algebras and combinatorics (Hong Kong, 1997), Springer, Singapore, 1999, pp. 25-36. · Zbl 0954.06001
[4] G. Brightwell and V. Patel, Average relational distance in linear extensions of posets, Discrete Math. 310 (2010), no. 5, 1016-1021. · Zbl 1230.05172
[5] B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600- 610. · Zbl 0025.31002
[6] D. Howard, R. Shull, N. Streib, and A. N. Trenk, The total linear discrepancy of an ordered set, Discrete Math. 310 (2010), no. 5, 1022-1025. · Zbl 1228.06002
[7] D. Kelly, The 3-irreducible partially ordered sets, Canad. J. Math. 29 (1977), no. 2, 367-383. · Zbl 0357.06004
[8] N. Streib, Dimension preserving contractions and a finite list of 3-irreducible posets, Order 29 (2012), no. 1, 165-176. · Zbl 1259.06004
[9] E. Szpilrajn, Sur l’extension de l’ordre partiel, Fundamenta Mathematicae 16 (1930), no. 1, 386-389. · JFM 56.0843.02
[10] W. T. Trotter Jr. and J. I. Moore Jr., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math. 16 (1976), no. 4, 361-381. · Zbl 0356.06007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.