Finding appropriate node labels for directed graphs

Question

I am searching for the correct terminology and a solution for the following problem:

Given a directed (hopefully acyclic) graph, assign for each node a number, s.t. the numbers of a path are decreasing from the start to the end node. The sequences should be consistent no matter which path in the graph is chosen.

Answer 1

If the graph contains a cycle, then this is impossible, that is, for any numbering there is a path such that the respective numbers won't be decreasing.

If the graph is acyclic, I can suggest three ways:

• Perform topological sorting and number the vertices according to the algorithm's output.
• Assign a number defined by $$ n(v) = \sum_{\text{path $P$ that starts at $v$}} \mathrm{length}(P).$$
• Define recursively $$ n(v) = 1+\max\Big(\big\{0\big\} \cup \big\{n(u) \mid (v,u) \in E\big\}\Big).$$

I hope this helps $\ddot\smile$