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

<p>This <a href="http://www.mth.msu.edu/~sagan/Papers/Old/sao.pdf">paper</a> studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, <em>acyclic orientations with a unique sink</em>. </p>

CC BY-SA 3.0
2012-07-25T01:32:35.893Z
And if you felt like going the other way, a vertex with only outgoing edges is a source.
Luke Mathieson
CC BY-SA 3.0
2012-07-24T17:35:07.853Z
2012-07-24T17:35:07.853Z
A.Schulz
<p>Consider an acyclic directed graph in which a traversal from any node in the graph must eventually end at some terminal node <em>R</em>.  Borrowing from tree-based vocabulary, I would tend call this the "root" of the graph, since all traversals eventually terminate there.  However, the term "<a href="http://mathworld.wolfram.com/RootedGraph.html" rel="nofollow">rooted graph</a>" seems to already be in use for something else.</p>

<p>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".</p>

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

CC BY-SA 3.0
2012-07-25T20:48:31.673Z
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.
Zsbán Ambrus
CC BY-SA 3.0
2012-07-25T23:13:11.763Z
@ZsbánAmbrus: Do you have a source for the term "pine"?
Jeffε
CC BY-SA 3.0
2012-07-26T08:11:56.703Z
@JeffE: Hmm, can I change my reply then?  Call such a tree an **inverse arborescence**, the source being Lovász, Combinatorial Problems and Exercises.
Zsbán Ambrus
CC BY-SA 4.0
2019-09-09T08:46:09.300Z
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.
Cyriac Antony
<graph-theory><co.combinatorics><terminology>
Term for a "rooted" directional graph?
apsillers
# Term for a "rooted" directional graph?

(Asked by: username_0 on 2012-07-24)

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](http://mathworld.wolfram.com/RootedGraph.html)" 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.

**Tags:** graph-theory, co.combinatorics, terminology
> **Comments:**
> **username_1**: 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.  
> **username_2**: @ZsbánAmbrus: Do you have a source for the term "pine"?  
> **username_1**: @JeffE: Hmm, can I change my reply then?  Call such a tree an **inverse arborescence**, the source being Lovász, Combinatorial Problems and Exercises.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2012-07-24. Score: 9 | Accepted answer

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](http://www.mth.msu.edu/~sagan/Papers/Old/sao.pdf) studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, *acyclic orientations with a unique sink*.

> **Comments:**
> **username_5**: And if you felt like going the other way, a vertex with only outgoing edges is a source.  

---

