Commutativity conditions for groups arising from acyclic directed graphs and posets

DOI10.1016/J.EJC.2010.10.009zbMATH Open1229.05111arXiv1110.3107OpenAlexW1964184952MaRDI QIDQ616389FDOQ616389

Authors: T. Bier, Imed Zaguia 

Publication date: 7 January 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $D=(V,A)$ be an acyclic digraph. For $xinV$ 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:Vightarrow[1,|V|]$ that has the property that for all $x,yinV$ if $(x,y)inA$, 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.

Full work available at URL: https://arxiv.org/abs/1110.3107

Recommendations

• Eulerian properties of non-commuting and non-cyclic graphs of finite groups
• scientific article; zbMATH DE number 524138
• ON THE GENUS OF THE COMMUTING GRAPHS OF FINITE NON-ABELIAN GROUPS
• Subgroups of graph groups
• scientific article; zbMATH DE number 1522659

zbMATH Keywords

partially ordered setsstrongly Eulerian graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Orbits of antichains in ranked posets
• Orbits of antichains revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• On orbits of antichains of positive roots
• A permutation group determined by an ordered set
• Title not available (Why is that?)

This page was built for publication: Commutativity conditions for groups arising from acyclic directed graphs and posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616389)