The cutting center theorem for trees

Abstract

We introduce the cutting number of a point of a connected graph as a natural measure of the extent to which the removal of that point disconnects the graph. The cutting center of the graph is the set of points of maximum cutting number. All possible configurations for the cutting center of a tree are determined, and examples are constructed which realize them. Using the lemma that the cutting center of a tree always lies on a path, it is shown specifically that (1) for every positive integer n, there exists a tree whose cutting center consists of all the n points on this path, and (2) for every nonempty subset of the points on this path, there exists a tree whose cutting center is precisely that subset.