Vertex-based and edge-based centroids of graphs

摘要

The sum of distances between all pairs of vertices, better known as the Wiener index for its applications in Chemistry, has been extensively studied in the past decades. One of the most important properties related to distance between vertices, in the form of the middle part of a tree called the “centroid”, has been thoroughly analyzed. Also arised in the study of Chemical Graph Theory is the edge Wiener index which studies the distances between edges. Various problems on this concept have been proposed and investigated, along with its correlation to the original Wiener index. We extend the study to the middle part of a tree in this note, showing interesting and sometimes rather unexpected observations on the so-called “edge centroid”. We also shed some more light on the relations between these distance-based graph invariants by investigating the behaviors of different centroids and their differences. Such edge-centroids are also compared with the vertex-based analogues in both trees and graphs. This leads to challenging questions for future work in this direction.