Centers and Medians of C(N) -Trees*
Sandra Hedetniemi, Stephen Hedetniemi, Peter Slater
Committee:
Technical Report(May 1980)
Keywords:

Given a connected graph G = (V,E), let d(u,v) denote the distance, or length of a shortest path, between vertices u and v. The center of G consists of the set of vertices u for which the value max {d(u,v): v ∈ V(G)} is a minimum. The median of G consists of the set of vertices u for which the sum σ d(u,v): v ∈ V(G), is a minimum; and the center and median subgraphs of G are the subgraphs induced by these two sets of vertices, respectively. Recently, the center subgraphs of a variety of different classes of graphs have been characterized; included among these are maximal outerplanar graphs, 2-trees, unicyclic graphs, cacti and c(4)-trees. This paper generalizes the result for c(4)-trees by completely characterizing the center subgraphs of all C(n)-trees. Several results about the possible median subgraphs of C(n)trees are also presented.

A C(n)-tree is a graph which can be constructed from a cycle of length n by a finite number of applications of the operation of adding another cycle of length n and identifying one of its edges with an edge already in the graph. These graphs are frequently used to describe classes of chemical compounds.