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$
5
  • $\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, 2017 at 12:39
  • $\begingroup$ If a new term would acceptable how about "the shadow width" of the tree? $\endgroup$ Dec 1, 2017 at 15:14
  • $\begingroup$ @ManfredWeis I don't get the idea behind "shadow width" :-( $\endgroup$
    – koalo
    Dec 3, 2017 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$ Dec 3, 2017 at 14:45
  • $\begingroup$ @ManfredWeis I like the idea, but since it is not so obvious I will use breadth. $\endgroup$
    – koalo
    Dec 5, 2017 at 10:40

1 Answer 1

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$
1
  • 2
    $\begingroup$ "breadth of a rooted tree" is used in at least one publication, and now also at findstat.org/St001058. $\endgroup$ Dec 4, 2017 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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