Corollary:

For each parameter k>0, there is a tree in which one node with degree k+1 and another with degree 2 both have the same closeness centrality of k*(k+1).

Proof:

We start with the construction of the tree: first, 2k+1 nodes are connected to a chain, and labeled from v

_{1}to v

_{2k+1}.Then, k nodes are added as neighbors to node v1. We will now determine the sum of distances distsum(v1) of node v1 to all other nodes in the tree. For each of the k added neighbors, the distance to v1 is 1. For the other nodes vi, the distance is i-1. Thus, distsum(v1) is given by k+1+2+...+2k =k+2k*(2k+1)/2 = k+2k^2+k=2k^2+2k=2k(k+1). Node vk+1 has two nodes in distance i each, for 1<=i<=k, summing up to 2*k(k+1)/2. The distance to the k additional neighbors of v1 is k+1, adding up to another summand of k*(k+1). Thus, distsum(vk+1) is also given by 2k(k+1).

## No comments:

## Post a Comment