Return to Answer

Update: I think actually there's actually a better repair than the one I mentioned above. The graph we're considering can actually be thought of as two complete graphs $K_d$ connected up in a certain way. (It's the tensor product $K_d \otimes K_2$.) So, you have several symmetries that flop two copies of $K_d$. If you fix one of these symmetries, you can get trees which are fixed by this symmetry by the following recipe:

Update: I think actually there's actually a better repair than the one I mentioned above. The graph we're considering can actually be thought of as two complete graphs $K_d$ connected up in a certain way. So, you have several symmetries that flop two copies of $K_d$. If you fix one of these symmetries, you can get trees which are fixed by this symmetry by the following recipe:

Update: I think actually there's actually a better repair than the one I mentioned above. The graph we're considering can actually be thought of as two complete graphs $K_d$ connected up in a certain way. (It's the tensor product $K_d \otimes K_2$.) So, you have several symmetries that flop two copies of $K_d$. If you fix one of these symmetries, you can get trees which are fixed by this symmetry by the following recipe:

1. Choose a rooted spanning tree for $K^d$.
2. Connect the two copies of $K^d$ by an edge between the two roots.

It seems like understanding the exact count of these spanning trees is going to involve understanding automorphisms of rooted trees on $d$ vertices. As far as I can tell, there is no closed form solution for this problem, but perhaps there are good enough asymptotics on the rooted tree problem to give good asymptotics for the problem of nets of cubes.

Update: I realized this construction can be extended a little bit. After you fix two opposite vertices and remove them, you're looking at a hyperoctohedron in $\mathbf{R}^{d-1}$. Now, instead of just taking any spanning tree, you can take a spanning tree and an automorphism fixing that spanning tree $\sigma$. If you let $\alpha$ be the automorphism reflecting the two opposite vertices we chose, then you can connect up your two chosen vertices to the chosen tree, and then you get that the whole thing is fixed by $\sigma \circ \alpha$.

I haven't taken the time to work this into the lower bound. However, it does show that my initial conjecture that no rotation fixes a spanning tree is off, which means there's a more subtle reason why certain automorphisms cannot fix a spanning tree.

I think that if you're careful enough, then doing this construction with spanning forests on the $d-1$ hyperoctohedron, and then connecting the forest into a tree with your two chosen vertices, should exhaust all the possibilities when $d$ is odd. When $d$ is even I think there's going to be special spanning trees that don't fit this construction.