Radius-Essential Edges in a Graph

Abstract

The graph resulting from contracting edge $e$ is denoted $G/e$. An edge $e$ is radius-essential if $rad(G/e)<rad(G)$. Let $c_r(G)$ denote the number of radius-essential edges in graph $G$. In this paper, we study realizability questions relating to the number of radius-essential edges, give bounds on $c_r(G)$ in terms of radius and order, and we characterize various classes of graphs achieving extreme values of $c_r(G)$.