out-trees and least upper boundness - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T19:50:05Z http://mathoverflow.net/feeds/question/75328 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75328/out-trees-and-least-upper-boundness out-trees and least upper boundness adamo 2011-09-13T16:21:27Z 2011-09-18T22:35:54Z <p>I am posting this on behalf of a friend:</p> <p>Frank Harary (in Graph Theory, 1969, p. 201) calls out-tree a digraph that (1) it has no semicycles and (2) it contains a root (source). In other words, an out-tree is a digraph such that the underlying graph is a tree with a distinguished root.</p> <p>On the other side, in his study of graph hierarchy, David Krackhardt has defined the property of least upper boundedness (LUB) in a digraph \$D\$: for any pair \$x, y\$ of vertices of \$D\$, there is a vertex \$z\$ which can reach both vertices and, moreover, \$z\$ is included in the path from any other such vertex reaching both \$x\$ and \$y\$.</p> <p>Apparently an out-tree satisfies LUB. What about the converse? Does anyone know of any theorem connecting the LUB property with the out-tree-ness of a digraph?</p> <p><strong>EDIT:</strong> Can one propose an example of weakly connected digraph without semicycles which satisfies the property of Least Upper Boundedness (LUB), while it is NOT an out-tree?</p> http://mathoverflow.net/questions/75328/out-trees-and-least-upper-boundness/75497#75497 Answer by Alon Amit for out-trees and least upper boundness Alon Amit 2011-09-15T09:05:00Z 2011-09-15T09:05:00Z <p>Perhaps I'm misunderstanding the definitions, but it seems like any lattice (in the poset sense) naturally defines a digraph which satisfies LUB but is, in most cases, not an out-tree. The simplest example is the digraph consisting of 4 vertices \$A, B_1, B_2, C\$ with edges from \$A\$ to each \$B_i\$ and from each \$B_i\$ to \$C\$. This has the LUB property far as I can tell, and the underlying graph is not a tree.</p>