Closeness Centrality of Asymmetric Trees and Triangular Numbers

The combinatorial problem in this paper is motivated by a variant of the famous traveling salesman problem where the salesman must return to the starting point after each delivery. The total length of a delivery route is related to a metric known as closeness centrality. The closeness centrality of a vertex v in a graph G was defined in 1950 by Bavelas to be C C ( v ) = | V ( G ) | − 1 S D ( v ) , where S D ( v ) is the sum of the distances from v to each of the other vertices (which is one-half of the total distance in the delivery route). We provide a real-world example involving the Metro Atlanta Rapid Transit Authority rail network and identify stations whose S D values are nearly identical, meaning they have a similar proximity to other stations in the network. We then consider theoretical aspects involving asymmetric trees. For integer values of k , we considered the asymmetric tree with paths of lengths k , 2 k , … , n k that are incident to a center vertex. We investigated trees with different values of k , and for k = 1 and k = 2 , we established necessary and sufficient conditions for the existence of two vertices with identical S D values, which has a surprising connection to the triangular numbers. Additionally, we investigated asymmetric trees with paths incident to two vertices and found a sufficient condition for vertices to have equal S D values. This leads to new combinatorial proofs of identities arising from Pascal’s triangle.