Actualmente estoy trabajando en el siguiente problema de teoría de grafos:
Para cada número entero $k \geq 1$ encontrar un grafo G conectado y no completo que no contenga ningún $P_{2k+2}$ con $\bar{d} (G) \geq 2k-0.0001$ .
En mi notación $P_{2k+2}$ significa la trayectoria de la longitud de la arista $2k+1$ y $\bar{d} (G)$ significa el grado medio de los vértices de $G$ .
Lo que he probado hasta ahora: para $k=1$ He dibujado una estrella. entonces el vértice central tiene grado $n$ El exterior $n$ los vértices tienen cada uno un grado $1$ . Esto nos da un grado medio de $\frac{2n}{n-1}$ . Para $n=20,000$ este término es mayor que el $2-0.0001$ de la pregunta. Ahora para $k=2$ Estoy atascado. Esencialmente empecé a ver mi estrella desde arriba como un árbol, donde mi vértice central es la raíz. Ahora puedo hacer mi árbol más alto, pero sólo uno más alto, ya que el camino más largo va de una hoja a través de la raíz a otra hoja. Pero en todas las variaciones de mi árbol nunca encontré la que me diera un grado medio de casi $4(=2k)$ pero tal vez simplemente no he encontrado el adecuado todavía.
Me gustaría tener una idea de cómo es ese gráfico, ya sea sólo para $k=2$ o para todos $k$ . Muchas gracias por su ayuda.
