About the maximum number of leaves adjacent to a vertex in a tree

Question

Let $T$ be a finite tree graph with the set of vertices $V(T)$. For an arbitrary vertex $ v \in V(T)$, I define $l(v)$ to be the number of leaves connected to $v$.

In my study, I need to define the following concept:

$$D(T) = \max_{v \in V(T)}l(v). $$

Obviously, $1 \leq D(T) \leq \Delta(T)$, which are achieved by (for example,) the path graphs and the star graphs, respectively. Here, I have two questions:

Question 1. Is there a common notation for $D(T)$?

Question 2. For a random tree $T$, is there some bounds (especially lower bound) for

$$ \dfrac{D(T)}{\vert V(T) \vert}, $$

or, what can one say about the average of the above ratio for the trees of a given order $n$?

Thanks in advance.

Answer 1

This seems like something that computation might shed some light on without too much effort:

So we need to calculate the average, over all labelled trees, of the maximum number of leaf-neighbours of a vertex in T.

Start with a couple of Sage functions: the first just calculates the value $D(T)$ for a tree passed in as an argument. It checks each vertex in turn, and if it is a leaf then it augments the counter associated with its unique neighbour.

def maxleafNeighbours(t):
    leafcount = [0 for i in range(t.num_verts())]
    for l in t.vertices():
        nb = t.neighbors(l)
        if len(nb) == 1:
            leafcount[nb[0]] = leafcount[nb[0]]+1
    return max(leafcount)

The second one goes through all the unlabelled trees $T$ on $n$ vertices, as computed by geng within SageMath, calculates $D(T)$ and adds $n!/|Aut(T)|$ to the count of labelled trees with that particular $D(T)$.

def maxleafData(nv):
    data = [0 for i in range(nv)]
    nvfactorial = factorial(nv)
    nauty_args = "-c " + str(nv) + " " + str(nv-1)
    for t in graphs.nauty_geng(nauty_args):
        val = maxleafNeighbours(t)
        data[val] = data[val] + nvfactorial/t.automorphism_group().order()
    return data

So if we run maxLeafData(6) the output is[0, 720, 450, 120, 0, 6] showing that 0 labelled trees on 6 vertices have $D(T) = 0$ but $720$ labelled trees on 6 vertices have $D(T) = 1$ and so on.

So what's the average value over all labelled trees on 6 vertices?

data = maxleafData(6)
float(sum([i*data[i] for i in range(len(data))]) / sum(data))
1.5509259259259258

So the average value of $D(T)$ is 1.55 taken over all labelled trees on 6 vertices. Let's try for larger values of 6.

datapoints = []
for v in range(6,18):
    data = maxleafData(v)
    avg = float(sum([i*data[i] for i in range(len(data))]) / sum(data))
    print (v,avg)
    datapoints.append((v,avg))
(6, 1.5509259259259258)
(7, 1.601832569762599)
(8, 1.615203857421875)
(9, 1.6481679057505914)
(10, 1.6749189)
(11, 1.7038043317645422)
(12, 1.7314162738607985)
(13, 1.7585077425737015)
(14, 1.7846671875609421)
(15, 1.8099355316779862)
(16, 1.8342600346899551)
(17, 1.8576535568845751)

What does this function look like?

sage.plot.scatter_plot.scatter_plot(datapoints)

Answer 2

Expanding on a comment upon OP's request:

To calculate the average over all unlabelled trees on $n$ vertices we can exploit the property that every finite tree has either a centroid or a bicentroid. This allows us to do most of the work with rooted trees. If $R(n, \ell, n')$ denotes the number of rooted trees on $n \ge 1$ vertices with leaf degree no greater than $\ell$ and largest subtree of the root having no more than $n'$ vertices, it's straightforward to observe that $$R(n, \ell, n') = \sum_{\substack{a_1 + 2a_2 + \cdots + n'a_{n'} = n-1 \\ a_i \ge 0, \, a_1 \le \ell}} \prod_i \binom{R(i, \ell, i-1) + a_i - 1}{a_i}$$ and then the number of unrooted trees on $n \ge 1$ vertices with leaf degree no greater than $\ell$ is $$U(n, \ell) = R(n, \ell, \lfloor \tfrac{n-1}{2} \rfloor) + [n \bmod 2 = 0] \binom{R(\tfrac n2, \ell, \tfrac n2-1) + 1}{2}$$ where the first term counts centroidal trees and the second term counts bicentroidal trees.

The average value of $D$ can then be calculated from the sum of $\ell \times (U(n, \ell) - U(n, \ell - 1))$.

$$\begin{array}{lll}n & \textrm{Average value of }D \\ 10 & \tfrac{ 273 }{ 106 } & 2.5754716981132075 \\ 20 & \tfrac{ 2442856 }{ 823065 } & 2.9679988822267984 \\ 30 & \tfrac{ 8019420586 }{ 2471811967 } & 3.2443489606262594 \\ 40 & \tfrac{ 139811830066568 }{ 40443361975927 } & 3.4569784319559744 \\ 50 & \tfrac{ 19140270453206756713 }{ 5272616851455754767 } & 3.6301273148497755 \\ 60 & \tfrac{ 1280181154745986534991397 }{ 339028211512423891688777 } & 3.7760313486450774 \\ 70 & \tfrac{ 45682358753537258004625609117 }{ 11707975085109065447981840723 } & 3.901815507930055 \\ 80 & \tfrac{ 854579683870799320987268538948428 }{ 212996951362776435118713593401621 } & 4.012168617452553 \\ 90 & \tfrac{ 1052333348443216545883200707797525831 }{ 256017690896079594101576682057492020 } & 4.1103930933834185 \\ 100 & \tfrac{ 2645869542867297259202984820861933788535463 }{ 630134658347465720563607281977639527019590 } & 4.198895438962389 \\ 110 & \tfrac{ 108056089072218514932463235689898358206661706828 }{ 25249910851886927651512825423644528049790467849 } & 4.279464181321791 \\ 120 & \tfrac{ 4497776622994307502713890704059983902896242709764300 }{ 1033152520048854877807430091756234770759903219425807 } & 4.353448823588622 \\ 130 & \tfrac{ 190236537379552120425249444657539623940185621178617944373 }{ 43021618115267465696869237333175709309993559077318319227 } & 4.421882432916701 \\ 140 & \tfrac{ 4078309455388167468312120474298736087566287820459068991699340 }{ 909206958384622679578660502467356659913467956631833840699407 } & 4.485567799254476 \\ 150 & \tfrac{ 353859940291181481656671781458954968017223608594806127078280803439 }{ 77854597863245593803382458410206749993828687629640764332291246132 } & 4.545138630254686 \\ 160 & \tfrac{ 3101913783575326643405047412687839902474001481340929721745853929687909 }{ 674167392856385067467973832042845361202496256060353873446102172056969 } & 4.601103251868655 \\ 170 & \tfrac{ 228641621023362551935592604670190188836671021946402528467487288932247650053 }{ 49129289916495568808202244198612600438761664756803878655268859041109764997 } & 4.65387595489334 \\ 180 & \tfrac{ 30578444138206708760484247282898045586908979222565303716833585814401220038148136 }{ 6500796542785541223708685574350747551917347770343511085479226714248864725046787 } & 4.703799593934697 \\ 190 & \tfrac{ 1372910069939378604123094002938718076965411651529591781815624762766787704284684359397 }{ 288963010503327141303436810960435570375562139390295662777413482341210574122229958615 } & 4.751161982801847 \\ 200 & \tfrac{ 31017734225457597933395862767739806385786293974719248494783415780971891125944778400164787 }{ 6467137160511131588828576867929731880706314086113664851345986440188472113397739601846462 } & 4.796207882346214 \\ 210 & \tfrac{ 352410710751392741057157079578720601593230993520260043369781528118511482826645957294214586621 }{ 72824952200684480254538422820789504157985441774873950082120417000877246368175883433716800531 } & 4.839147848394749 \\ 220 & \tfrac{ 128797282048478184965954075556518131019553531235842408067945212679480184453626360695959830028141707 }{ 26391994208692151383402347175682684406164602489756559480467014002726855337575585275144893746100626 } & 4.880164834457983 \\ 230 & \tfrac{ 5912096543789000433038220579892213157945368680400433791633085366777082281086933708715575870840324133777 }{ 1201787513172706269909923669062213294532536027184453127982144782354836198036307712699780197770445921657 } & 4.919419181000748 \\ 240 & \tfrac{ 272563652060306897395747185358655803738754221966330221551036734394657565391873216737292786227592630120780361 }{ 54985024966026897870269075763444229658301263057496157167354274092275126613889793234171034121437216543398430 } & 4.957052437981311 \\ \end{array} $$