SPANNING SUBGRAPHS OF A HYPERCUBE .4. ROOTED TREES

A rooted spanning tree T of a hypercube Q(n) with root at origin u = ( 0, 0,.., 0) has a function g : E(T) --> {-1,+1} defined as follows. Fo r each edge xy of T with d(T)(U,X) < d(T)(u,y), let g(xy) = SIGMA(y(i) - x(i)). Another function f is defined by f(T, u) = SIGMAg(xy). We ob serve that f depends on the embedding of T, is odd-valued, and we obta in sharp bounds for f. We derive an odd-interpolation theorem for the values of f over all spanning trees of Q(n).