Edge-added Eccentricities of Vertices in a Graph

Abstract

The eccentricity of a vertex $v$ in a connected graph $G$ is the distance between $v$ and a vertex farthest from $v$. For a vertex $v$, we define the edge-added eccentricity of $v$ as the minimum eccentricity of $v$ in all graphs $G+e$, taken over all edges $e$ in the complement of $G$. A graph is said to be edge-added stable (or just stable) if the eccentricity and the edge-added eccentricity are the same for all vertices in the graph. This paper describes properties of edge-added eccentricities and edge-added stable graphs.