# Formal definition on graph levels

I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.

The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.

Level 0 : node 0

Level 1 : node 3, node 4

Level 2 : node 1, node 2

Level 3 : node 5 • Given a source $s$, can you define the level $L_i = \{ v \mid d(s,v) = i \}$? In general, it makes little sense to say you want a formal definition of something, since you are free to make any kind of definitions you want. It depends on what you want to capture and do with the definition. – Juho May 28 '17 at 13:11
• But does this definition have a formal name? – user72738 May 28 '17 at 13:18
• Its formal name is whatever you give it, like maybe a level structure. – Juho May 28 '17 at 13:23
• I'm sorry if I'm not expressing myself clear. What I'm asking for is a mainstream name for the definition so that I can google on it. – user72738 May 28 '17 at 13:27

## 2 Answers

A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for example the Wikipedia article on graded poset.

This is sometimes known as a level structure, and they come up in e.g., certain algorithmic applications.