Skip to main content
4 of 4
Added top-level tag
gmvh
  • 3.1k
  • 6
  • 27
  • 45

Name for generalization of trees to digraphs

One definition of tree in graph theory could be as follows:

A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.

This suggest a possible definition of "directed tree":

A "directed tree" is a directed graph for which there is a unique directed path between any pair of vertices.

Question: Is there an established name for the "directed trees" defined above?

Note that these "directed trees" are not arborescences (rooted directed trees). For example, a directed cycle is a "directed tree" in the above sense; and indeed all "directed trees" in the above sense are basically trees of directed cycles.

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76