Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^{n-2}$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1\leq k \leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?
I am mainly interested for $n=p$ being an odd prime and $p^{p-3}$ spanning trees. But any known results/approaches would be helpful.
As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.
For $k=1$, use a cycle graph.
Here are solutions for $k\in(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.
The Petersen graph spanning tree count is $2\times 10^3$.
The Chang graphs spanning tree count is $2 \times 28^{19}$.
The Tietze graph spanning tree count is $5 \times 12^{3}$.
The Gen Quadrangle(2,2) graph spanning tree count is $\frac{15^8}{3}$.
Here are solutions for $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})$.
Here are a few graphs with $(p-2) p^{p-3}$ spanning trees.
The Paley graphs have $\frac{n-1}{4}^\frac{n-1}{2} \times n^\frac{n-3}{2}$ spanning trees.