Skip to main content
MathOverflow

Return to Question

clarification
Source Link
adamo
adamo
  • 343
  • 1
  • 5
  • 14

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?

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?

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?

Source Link
adamo
adamo
  • 343
  • 1
  • 5
  • 14

out-trees and least upper boundness

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?