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.

$\endgroup$
  • 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 Jul 25 '12 at 20:48
  • $\begingroup$ @ZsbánAmbrus: Do you have a source for the term "pine"? $\endgroup$ – Jeffε Jul 25 '12 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 Jul 26 '12 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 Sep 9 at 8:46
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.

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

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.