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 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 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>