Search

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. [ABSTRACT FROM AUTHOR]