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

Improve this question
$\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
    Commented Dec 1, 2017 at 12:39
  • $\begingroup$ If a new term would acceptable how about "the shadow width" of the tree? $\endgroup$
    – Manfred Weis
    Commented Dec 1, 2017 at 15:14
  • $\begingroup$ @ManfredWeis I don't get the idea behind "shadow width" :-( $\endgroup$
    – koalo
    Commented 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$
    – Manfred Weis
    Commented 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
    Commented Dec 5, 2017 at 10:40

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .