Let $T$ be a rooted tree with root $r$. Say an ordering $v\_1,\ldots,v\_n$ of the vertices of $T$ is a *search order* if $v\_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v\_j$ is the parent of $v\_i$. In other words, parents are explored before their children in the order. 


For a given search order $v\_1,\ldots,v\_n$, let $w(v\_i)=\max(j:v\_iv\_j \in E(T))-\min(j:v\_jv\_i \in E(T))$. The max is the time the last child of $v\_i$ is explored, and the min is the time the parent of $v\_i$ is explored. Say the width of the order is $\max(w(v\_i):1 \leq i \leq n)$, and say the width of $T$ is the minimum width of an ordering of $T$. 


Is anything known about the width? Is it a known concept under another name? Have any theorems been proved about it? Any equivalent characterizations/definitions? Any useful bounds~~, perhaps in terms of the maximum degree of $T$~~? 


**Edit**: This is the directed bandwidth, as David Eppstein points out below. I'm still interested in any bounds -- perhaps some upper bound with a simple form, perhaps even with an approximation guarantee? 



Theorems about the directed bandwidth of a rooted tree?
What you call width is known more specifically as "directed bandwidth". It's known to be NP-complete even for trees; see [Complexity Results for Bandwidth Minimization, M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, SIAM Journal on Applied Mathematics Vol. 34, No. 3 (May, 1978), pp. 477-495](http://www.jstor.org/stable/2100947). The hardness of the undirected case for trees (without the parent-child ordering constraint) is detailed in section 8 of the paper, and in section 9 they claim without giving a detailed proof that it's also hard in the directed case.


