From a nomenclature standpoint, I am wondering if there is a name for a class of directed graph that has only one path to any given parent.

I can visualize this shape as an upside down tree that may or may not have a root, kind of like this:

enter image description here

In looking at this, I can see it is not really an upside down tree.

Is there a name for this type of graph? Again the rules are:

  • graph is directed

  • there are no cycles

  • nodes can share children

  • no node can have multiple paths to the same parent

Note that these rules work the same in both directions. For example, if we take the graph shown above and reverse the direction of all the arrows, then the rules are still satisfied. What is the name of this thing?

  • $\begingroup$ If there were at least two paths to the same parent of a vertex, would you not have a cycle, at least in the underlying undirected graph? $\endgroup$ – Samuel Yusim Jun 23 '16 at 15:09
  • $\begingroup$ @SamuelYusim Yes, but this question is about directed graphs, not undirected graphs. $\endgroup$ – Tyler Durden Jun 23 '16 at 15:10

An orientation such that for every $u-v$ path there exists a $v-u$ path is called a strong orientation. Conversely, an orientation that only has either a $u-v$ or a $v-u$ path is a weak orientation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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