A Generalized Distance in Graphs and Centered Partitions
Cristian Lenart · SIAM Journal on Discrete Mathematics · 1998
This paper is concerned with a new distance in undirected graphs with weighted edges, which gives new insights into the structure of all minimum spanning trees of a graph.This distance is a generalized one, in the sense that it takes values in a certain Heyting semigroup. More precisely, it associates with each pair of distinct vertices in a connected component of a graph the set of all paths joining them in the minimum spanning trees of that component. A partial order and an addition of these sets of paths are defined. We show how general algorithms for path algebra problems can be used to compute the generalized distance. Some theoretical problems concerning this distance are formulated. The main application of our generalized distance is related to recent clustering procedures. Given a connected graph with weighted edges and certain vertices labeled as centers, we define a centered forest to be a spanning forest with exactly one center in each tree component. A partition of the vertices determined by a minimum centered forest will be called a centered partition. These partitions are characterized in terms of the generalized distance, and some corollaries are derived.