Where is the Middle of a Tree?

 

Abstract

Notions of the middle of a graph or the outer fringes of a graph appear in the study of the optimal location(s) for placement of facilities in a network.  Examples include, among others, an emergency installation, a supply depot, a switching center, a pumping station, an obnoxious dump, and a communications center.  Optimality depends on criteria usually involving some idea of distance and varies according to the application.  Weighted graphs, often referred to as networks, provide a context for studying these types of problems.  Ordinary graphs arise in cases in which all vertex weights are the same, all edge weights are the same, clients are located at vertices and placement of facilities is restricted to vertices.  So, many combinatorially inclined researchers have focused on the study of centrality (and anti-centrality) in graphs, particularly in trees.

In this talk we will discuss centrality in trees in order to propose answers to the question "where is the middle of a tree?" We will begin with two classical ideas propose by C. Jordan in 1869, the center and the branch-weight centroid.  Then we will treat, in turn, other notions and their relationships including the median, the security center, the telephone center, the accretion center, the set of weight balanced vertices, the latency center, and the distance balanced vertices.  We contrast these central sets with some other central concepts, some involving one or two parameters and some involving very different structures than the previous central sets.

This topic is a very accessible branch of applicable combinatorics, rich in problems, and offering an occasional surprise.