Skip to main content
MathOverflow

Return to Question

Added top-level tag
Link
gmvh
gmvh
  • 3.1k
  • 6
  • 27
  • 45
added 407 characters in body; edited tags; edited title
Source Link
Sam Hopkins
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Name for direct generalization of spanning trees to digraphs

If we reformulate theOne definition of spanning treestree in connected symmetric pathsgraph theory could be as follows:

connected graphs that containA tree is a(n undirected) graph for every unorderedwhich there is a unique (undirected) path between any pair of vertices a unique connecting paths.

then that definition carries directly over to digraphs, albeit withThis suggest a minor adaptionpossible definition of "directed tree":

connected graphs that containA "directed tree" is a directed graph for every orderedwhich there is a unique directed path between any pair of vertices a unique connecting paths.

Question:
is Is there an established name for digraphs that satisfy the "directed trees" defined above condition of having?

Note that these "directed trees" are not arborescences (rooted directed trees). For example, a unique connecting path for every ordered pairdirected cycle is a "directed tree" in the above sense; and indeed all "directed trees" in the above sense are basically trees of vertices?directed cycles.

Name for direct generalization of spanning trees to digraphs

If we reformulate the definition of spanning trees in connected symmetric paths as:

connected graphs that contain for every unordered pair of vertices a unique connecting paths

then that definition carries directly over to digraphs, albeit with a minor adaption:

connected graphs that contain for every ordered pair of vertices a unique connecting paths

Question:
is there an established name for digraphs that satisfy the above condition of having a unique connecting path for every ordered pair of vertices?

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.

edited tags
Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76
Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76