Abstract
The signature of a spanning tree T of the n-dimensional cube Q(n) is the n-tuple sig(T) = (a(1), a(2), ..., a(n)) such that a(i) is the number of edges of T in the ith direction. We characterise the n-tuples that can occur as the signature of a spanning tree, and classify a signature S as reducible or irreducible according to whether or not there is a proper nonempty subset R of [n] such that restricting S to the indices in R gives a signature of Q(vertical bar R vertical bar). If so, we say moreover that S and T reduce over R.
We show that reducibility places strict structural constraints on T. In particular, if T reduces over a set of size r then T decomposes as a sum of 2(r) spanning trees of Q(n-r) together with a spanning tree of a certain contraction of Q(n), with underlying simple graph Q(r). Moreover, this decomposition is realised by an isomorphism of edge slide graphs, where the edge slide graph of Q(n) is the graph epsilon(Q(n)) on the spanning trees of Q(n), with an edge between two trees if and only if they are related by an edge slide. An edge slide is an operation on spanning trees of the n-cube given by "sliding" an edge of a spanning tree across a 2-dimensional face of the cube to get a second spanning tree.
The signature of a spanning tree is invariant under edge slides, so the subgraph epsilon(S) of epsilon(Q(n)) induced by the trees with signature S is a union of one or more connected components of epsilon(Q(n)). Reducible signatures may be further divided into strictly reducible and quasi-irreducible signatures, and as an application of our results we show that epsilon(S) is disconnected if S is strictly reducible. We conjecture that the converse is also true. If true, this would imply that the connected components of epsilon(Q(n)) can be characterised in terms of signatures of spanning trees of subcubes.