A Sharp Lower Bound for the Number of Connectivity-Redundant Nodes

Abstract

We call a node of a simple graph $connectivity-redundant$ if its removal does not diminish the connectivity. Studying the distribution of such nodes in a CKL-graph, i.e., a connected graph $G$ of order $\ge 3$ whose connectivity $\kappa$ and minimum degree $\delta$ satisfy the inequality $\kappa \ge (\frac{3\kappa –1}{2})$, we obtain a best lower bound, sharp for any $\kappa >1$, for the number of connectivity-redundant nodes in $G$, which is $\kappa +1$ or $\kappa +2$ according to whether $\kappa$ is odd or even, respectively. As a by-product we obtain a new proof of an old theorem of Watkins concerning node-transitive graphs.