Craig Larson
Radius and Independence

Abstract

The eccentricity of a vertex v in a graph G is the maximum distance from v to any other vertex of the graph. The radius of a connected graph is the minimum eccentricity of any of its vertices. A connected graph is radius-critical if the removal of any vertex either disconnects the graph or decreases the radius of the remaining graph. In this talk, an interesting characterization, due to Siemion Fajtlowicz, of radius-critical graphs is discussed, as well as its implications for the structure of any graph, and a conjecture of the program Graffiti (proved by Erdös, Saks, and Sos).