Sobre el número máximo de hojas adyacentes a un vértice en un árbol

Question

Dejemos que $T$ sea un grafo arbóreo finito con el conjunto de vértices $V(T)$ . Para un vértice arbitrario $ v \in V(T)$ Defino $l(v)$ para ser el número de hojas conectadas a $v$ .

En mi estudio, necesito definir el siguiente concepto:

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

Obviamente, $1 \leq D(T) \leq \Delta(T)$ que se consiguen, por ejemplo, con los grafos de trayectorias y los grafos de estrellas, respectivamente. Aquí, tengo dos preguntas:

Pregunta 1. ¿Existe una notación común para $D(T)$ ?

Pregunta 2. Para un árbol aleatorio $T$ ¿hay algún límite (especialmente el más bajo) para

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

o bien, qué se puede decir de la media de la relación anterior para los árboles de un orden determinado $n$ ?

Gracias de antemano.

Answer 1

Esto parece algo que la computación podría arrojar algo de luz sin demasiado esfuerzo:

Así que tenemos que calcular la media, sobre todos los árboles etiquetados, del número máximo de vecinos de hoja de un vértice en T.

Comienza con un par de funciones de Sage: la primera sólo calcula el valor $D(T)$ para un árbol pasado como argumento. Comprueba cada vértice por turnos y, si es una hoja, aumenta el contador asociado a su único vecino.

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)

El segundo recorre todos los árboles no etiquetados $T$ en $n$ vértices, calculados por geng dentro de SageMath, calcula $D(T)$ y añade $n!/|Aut(T)|$ al recuento de árboles etiquetados con ese $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

Así que si ejecutamos maxLeafData(6) la salida es [0, 720, 450, 120, 0, 6] mostrando que 0 árboles etiquetados en 6 vértices tienen $D(T) = 0$ pero $720$ los árboles etiquetados en 6 vértices tienen $D(T) = 1$ y así sucesivamente.

¿Cuál es el valor medio de todos los árboles etiquetados en 6 vértices?

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

Así, el valor medio de $D(T)$ es 1,55 tomado sobre todos los árboles etiquetados en 6 vértices. Probemos con valores mayores de 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)

¿Qué aspecto tiene esta función?

sage.plot.scatter_plot.scatter_plot(datapoints)

Answer 2

Ampliando un comentario a petición del OP:

Para calcular la media de todos los sin etiquetar árboles en $n$ vértices podemos explotar la propiedad de que todo árbol finito tiene un centroide o un bicentroide. Esto nos permite hacer la mayor parte del trabajo con árboles enraizados. Si $R(n, \ell, n')$ denota el número de árboles enraizados en $n \ge 1$ vértices con grado de hoja no superior a $\ell$ y el mayor subárbol de la raíz que no tenga más de $n'$ vértices, es sencillo observar que $$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}$$ y luego el número de árboles sin raíces en $n \ge 1$ vértices con grado de hoja no superior a $\ell$ es $$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}$$ donde el primer término cuenta los árboles centroidales y el segundo término cuenta los árboles bicentroidales.

El valor medio de $D$ se puede calcular a partir de la suma de $\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} $$