MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am posting this on behalf of a friend:

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.

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

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?

EDIT: 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?

share|cite|improve this question

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.

share|cite|improve this answer
Lattices contain semicycles. I've edited the question to clarify what he's asking a bit – adamo Sep 18 '11 at 22:39
I'm still very confused. Yes, lattices contain semicycles, that's just the point - you were asking if every LUB graph is a (kind of) tree, and it isn't. You now changed the question to ask if every connected digraph without semicycles (which further satisfies LUB) must be a (kind of) tree. Well, it is, by definition, right? The underlying undirected graph certainly is a tree (connected and cycle free). This is just an out-tree except that we haven't chosen a specific root. – Alon Amit Sep 19 '11 at 16:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.