Skip to main content
top-level tag
Link
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38
Source Link
koalo
  • 195
  • 6

Term for the maximum number of vertices per depth of a rooted tree

I am searching for a term that describes the following property of a rooted tree (or actually a DODAG, but that should not make a difference) and preferably for a publication that uses/introduces this term.

Given a tree $T=(V,E)$ with a dedicated root $v_0 \in V$. The depth $\delta(v)$ of a vertex $v$ is the length of the (shortest) path to $v_0$. The depth of the tree is denoted as $\delta_{max} = max_{v \in V}\,\,\delta(v)$. The set of vertices with the same depth is denoted as $L(d) = \{ v \,|\, \delta(v) = d\}$. What is an appropriate term for the maximum number of elements in the $L(d)$, that is $W = max_{d \in [0,\delta_{max}]}\, |L(d)|$?

An exemplary tree

In the above example, the number would be $W=5$, because there are 5 vertices with depth 3. Potential terms that came to my mind where tree width, but that is actually 1 for all trees (with at least two vertices) or fan-out, but that is defined per vertex and the fan-out of a tree is the maximum over all fan-outs of the vertices (3 in the above example).