2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Closely related: en.wikipedia.org/wiki/Arborescence_(graph_theory) en.wikipedia.org/wiki/Multitree $\endgroup$
    – RobPratt
    Commented Feb 9 at 20:58
  • $\begingroup$ @RobPratt the examples have no strongly connected, i.e. are special kinds of DAGs whereas the suggested generalizations of trees are strongly connected. $\endgroup$
    – Manfred Weis
    Commented Feb 9 at 21:18
  • $\begingroup$ In contrast to undirected trees, where the cardinality of edges is fixed to $n-1$, it can be anything from $n$ to $2(n-1)$ in the directed case; the extremes being a directed Hamilton cycle, resp. an undirected tree after having replaced each of its undirected edges with a pair of antiparallel arcs. $\endgroup$
    – Manfred Weis
    Commented Feb 10 at 12:27

1 Answer 1

Reset to default
4
$\begingroup$

Now I remember that I do know what these digraphs are called. A "directed tree" in the sense defined above is usually called a directed cactus. See for example Section 3 of "Remarks on Hamiltonian properties of powers of digraphs" by Günter Schaar (https://doi.org/10.1016/0166-218X(94)90107-4):

A strongly connected (finite) digraph G, each edge of which is contained in at most (and thus, in exactly) one directed cycle in G, is called a directed cactus.

I learned this terminology from Section 2.5 of "CoEulerian graphs" by Matthew Farrell and Lionel Levine (https://doi.org/10.1090/proc/12952). They show these directed cactuses are exactly the digraphs that are both Eulerian and coEulerian, where "coEulerian" is a new concept they introduce in that paper.

I guess technically it is a little unclear whether loops are allowed (for your "directed trees" or for directed cactuses). That should just be specified.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Loops in the sense of directed Hamilton cycles are allowed; ruling them out would be unnatural and allowing them makes it possible to develop heuristics for ATSPs that start from a greedily constructed directed tree. $\endgroup$
    – Manfred Weis
    Commented Feb 10 at 15:43
  • $\begingroup$ I mean loops in the usual sense, an edge from a vertex to itself: en.wikipedia.org/wiki/Loop_(graph_theory). $\endgroup$
    – Sam Hopkins
    Commented Feb 10 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .