Welcome to MathOverflow

Question

1

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?

edited Sep 18 2011 at 22:35

asked Sep 13 2011 at 16:21

adamo
125●1●7

Alon Amit · Answer 1 · 2011-09-15 09:05:00Z UTC

3

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.

answered Sep 15 2011 at 9:05

Alon Amit
4,035●15●40

	Lattices contain semicycles. I've edited the question to clarify what he's asking a bit – adamo Sep 18 2011 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 2011 at 16:22

out-trees and least upper boundness

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.