Tree of paths from a vertex in a graph Given a directed graph $G=(V,E)$, and one of its vertices $v\in V$, the set of finite paths in $G$ that start with $v$ can be seen as a tree, if we merge paths with a common prefix.
That tree is not necessarily a subgraph of $G$: if $G$ has cycles, paths can visit vertices several times, so the tree could be infinite for finite $G$. 
Question: what would you call that tree?
 A: *

*Here is a recent paper that seems to be exactly what you want in the undirected case, but may or may not be a good paper: Nonbacktracking expansion of finite graphs. They call it the "nonbacktracking expansion." Excerpt from the abstract:

... For an arbitrary finite, connected, undirected graph we construct
  an infinite tree having the same local structural properties as this finite graph, when observed by
  a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of
  the Bethe lattice. ...

The lack of good references strikes me as a red flag, and I feel there should be a better reference out there, but maybe it is one place to start.

*Let $\text{Tree}(G,v)$ denote the tree of paths in $G$ starting from vertex $v$, which you define in your post. The map $(G,v) \mapsto \text{Tree}(G,v)$ is a functor from the category of directed rooted graphs to itself.

*Maybe there is some nice model-theoretic characterization of $\text{Tree}(G,v)$: Consider the theory $\mathcal{T}$ over the language of a single binary relation $E$ (directed edge relation), defined by $\mathcal{T} = \{\varphi_1, \varphi_2, \varphi_3, \ldots\}$, where $\varphi_i$ says "there are no $i$-cycles". $\mathcal{T}$ is the theory of directed acylic graphs. Let $\mathcal{T}_n = \{\varphi_1, \ldots, \varphi_n\}$. Then for any $G, v$ and any $n$, there exists $G_n, v_n$ such that $\text{Tree}(G,v) = \text{Tree}(G_n, v_n)$ and $G_n \vDash \mathcal{T}_n$. So the $\text{Tree}$ graph in a way extracts first-order information from $G$ that is not a result of $G$ having cycles.
