Grafos con un número determinado de árboles de distribución

Question

Fijar un número natural $n$ . Entonces un árbol en $n$ vértices tiene $1=n^0$ árbol de expansión, un ciclo en $n$ Los vértices que se extienden tienen $n = n^1$ y el gráfico completo en $n$ vértices tiene $n^{n-2}$ árboles de expansión. Estos son los casos extremos triviales para lo que estoy considerando. Es decir, para lo que naturalmente $1\leq k \leq n-2$ ¿existe un gráfico en $n$ vértices con $n^k$ ¿Árboles de distribución? Y si es así, ¿qué aspecto tiene el gráfico (en el sentido de algún tipo de caracterización)?

Me interesa principalmente por $n=p$ siendo un primo de impar y $p^{p-3}$ árboles de expansión. Pero cualquier resultado/enfoque conocido sería útil.

Como apunte, no es difícil encontrar un gráfico con $p = 2k+1$ vértices y $p^k$ árboles de expansión. Este es el único caso no trivial que he podido averiguar.

Answer 1

Para $k=1$ Utiliza un gráfico de ciclo.

Aquí están las soluciones para $k\in(2,3,4,5,9,24)$ . En la parte superior está $v^k$ como el recuento de los árboles de extensión, con $v$ como el número de vértices.

El recuento del árbol de spanning del gráfico de Petersen es $2\times 10^3$ .
El recuento del árbol de expansión de los gráficos Chang es $2 \times 28^{19}$ .
El recuento del árbol de expansión del grafo de Tietze es $5 \times 12^{3}$ .
El recuento del árbol de expansión del gráfico Gen Quadrangle(2,2) es $\frac{15^8}{3}$ .

Aquí están las soluciones para $k \in (\frac{8}{3}, \frac{10}{3}, \frac{17}{4}, \frac{25}{4}, \frac{31}{4}, \frac{35}{4},\frac{21}{2}, \frac{112}{5}, \frac{116}{3})$ .

Aquí hay algunos gráficos con $(p-2) p^{p-3}$ árboles de expansión.

Los gráficos de Paley tienen $\frac{n-1}{4}^\frac{n-1}{2} \times n^\frac{n-3}{2}$ árboles de expansión.