1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Lattices contain semicycles. I've edited the question to clarify what he's asking a bit $\endgroup$
    – adamo
    Commented Sep 18, 2011 at 22:39
  • $\begingroup$ 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. $\endgroup$
    – Alon Amit
    Commented Sep 19, 2011 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .