2
$\begingroup$

Consider an acyclic directed graph in which a traversal from any node in the graph must eventually end at some terminal node R. Borrowing from tree-based vocabulary, I would tend call this the "root" of the graph, since all traversals eventually terminate there. However, the term "rooted graph" seems to already be in use for something else.

Is there a term I can use to describe this property? The best way I can describe the graph at present is a "multi-parented directed tree" -- all nodes point toward the root, but, unlike a directed tree, nodes may have more than one parent. I don't like this terminology, though, as it seems like an abuse of the term "tree".

I considered "hierarchical graph", but a node can have more than one outgoing vertex, so I think that may disqualify it from being hierarchical.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If it's a tree, call such a directed tree with each edge oriented towards the root an inverse pine. (A pine is a tree with every edge is oriented away from the root.) If it's not a tree, then I have no idea. $\endgroup$
    – Zsbán Ambrus
    Commented Jul 25, 2012 at 20:48
  • $\begingroup$ @ZsbánAmbrus: Do you have a source for the term "pine"? $\endgroup$
    – Jeffε
    Commented Jul 25, 2012 at 23:13
  • $\begingroup$ @JeffE: Hmm, can I change my reply then? Call such a tree an inverse arborescence, the source being Lovász, Combinatorial Problems and Exercises. $\endgroup$
    – Zsbán Ambrus
    Commented Jul 26, 2012 at 8:11
  • $\begingroup$ A rooted graph is usually identified with a directed graph (with the root being the 'source'). It is perfectly reasonable to treat the root as the 'sink' instead. $\endgroup$
    – Cyriac Antony
    Commented Sep 9, 2019 at 8:46

1 Answer 1

Reset to default
9
$\begingroup$

I don't know if these graphs have a common name. But I think, one would call vertices with no outgoing edge rather a sink than a root.

This paper studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, acyclic orientations with a unique sink.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ And if you felt like going the other way, a vertex with only outgoing edges is a source. $\endgroup$
    – Luke Mathieson
    Commented Jul 25, 2012 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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