Centrality of Paths and Vertices in a Graph: Cores and Pits

摘要

As criteria for the selection of a site at which to locate a facility in a graph or network, measures of the suitability of a vertex v include the eccentricity e(v), the distance d(v), and, when the graph is a tree, the branch weight bw(v). A vertex at which function e, d, or bw is minimized is called a center, a median, or a (branch weight) centroid, respectively. For a tree T the functions e, d, and bw are convex functions on vertex set V(T); and, in general, they measure how central a vertex is relative to the other vertices. The nature of the facility to be constructed (such as a pipeline) could necessitate selecting a structure (such as a path) rather than just a point at which to locate the facility. Similarly, the facility may be required to service structures or areas within the graph. Functions e, d, and bw can be applied to paths P in the graph and (minimum) paths P for which e(P), d(P), and bw(P) are minimized are called path centers, cores, and spines, respectively. With emphasis on these central paths, central structures are examined. 3 figures. (ERA citation 05:031438)