Spanning subgraphs of a hypercube. IV: Rooted trees (Q1310235): Difference between revisions

Let \(T\) be a spanning tree of the hypercube \(Q_ n\), rooted at the origin \(u_ 0\). Define a function \(g:E(T) \to\{-1,+1\}\) as follows: If \(e=xy \in E(T)\) is such that \(d_ T(x,u_ 0)<d_ T(y,u_ 0)\), then \(g(e)=\sum (y_ i-x_ i)\). Define \(f(T,u_ 0)=\sum_{e \in E(T)} g(e)\). The authors prove that \(2n+1-2^ n \leq f(T,u_ 0)\leq 2^ n-1\) and that the bounds are tight. Given a spanning tree \(T\) of \(Q_ n\), the root \(u_ 0\) can be varied over the \(2^ n\) possible vertices. Denoting the corresponding values of \(f(T,u_ 0)\) by \(f_ j(T)\), \(1 \leq j \leq 2^ n\), the authors further prove that \(\sum^{2^ n}_ 1f_ j(T)=n2^ n\). If \(S=\{T_ 1,\dots,T_ s\}\) is the set of spanning trees of \(Q_ n\) and if \(k\) is any positive odd integer between \(f(T_ i)\) and \(f(T_ j)\), for \(1 \leq i\), \(j \leq s\), then the authors prove that there is a spanning tree \(T_ h\) in the set such that \(f(T_ h,u_ 0)=k\).