1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I wouldn't object to "width" as an ad hoc usage, but it isn't standard. If the tree were generated by a branching process you might call it the size of the largest generation. $\endgroup$ – Ben Barber Dec 1 '17 at 12:39
  • $\begingroup$ If a new term would acceptable how about "the shadow width" of the tree? $\endgroup$ – Manfred Weis Dec 1 '17 at 15:14
  • $\begingroup$ @ManfredWeis I don't get the idea behind "shadow width" :-( $\endgroup$ – koalo Dec 3 '17 at 13:47
  • $\begingroup$ @koalo the idea behind it was an analogy to a biological tree with the sun vertically above it; the shadow would then resemble the maximal width; o.k. the analogy is not obvious and has weaknesses, so just ignore my suggestion. $\endgroup$ – Manfred Weis Dec 3 '17 at 14:45
  • $\begingroup$ @ManfredWeis I like the idea, but since it is not so obvious I will use breadth. $\endgroup$ – koalo Dec 5 '17 at 10:40
2
$\begingroup$

Breadth might be better? As in breadth first search. The set of vertices of the same depth $L(d)$ seems to be denoted a level.

$\endgroup$
  • 2
    $\begingroup$ "breadth of a rooted tree" is used in at least one publication, and now also at findstat.org/St001058. $\endgroup$ – Martin Rubey Dec 4 '17 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.