On the average distance of the hypercube tree

Abstract

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)− 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.

Keywords:

• average distance
• total distance
• average delay
• wiener index
• hypercube tree

2000 AMS Subject Classification: :

• 05C12
• 05C05
• 05C85
• 05C90