Closeness Centrality of Asymmetric Trees and Triangular Numbers

Nytha Ramanathan, Eduardo Ramirez, Dorothy Suzuki-Burke and Darren A. Narayan ()
Additional contact information
Nytha Ramanathan: School of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USA
Eduardo Ramirez: School of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USA
Dorothy Suzuki-Burke: School of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USA
Darren A. Narayan: School of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623, USA

Mathematics, 2024, vol. 12, issue 19, 1-15

Abstract: 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.

Keywords: graph distance; closeness centrality (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/19/2994/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/19/2994/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:19:p:2994-:d:1486034

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().