On the average distance of the hypercube tree
Muhammad H. Alsuwaiyel · International Journal of Computer Mathematics · 2008
Given a graph G on n vertices, the total distance of G is defined as σ G=(1/2) ∑ u, v∈V(G) d(u, v), where d(u, v) is the number of edges in a shortest path between u and v. We define the d-dimensional hypercube tree T d and show that it has a minimum total distance σ (T d )=2σ (H d )−=(dn 2/2)− over all spanning trees of H d , where H d is the d-dimensional binary hypercube. It follows that the average distance of T d is μ(T d )=2 μ(H d )−1=d (1+1/(n−1))−1.