Extreme Values of the Edge-Neighbor-Connectivity

Abstract

The edge-neighbor-connectivity of a graph $G$ is the minimum size of all edge-cut-strategies of $G$, where an edge-cut-strategy consists of a set of common edges of double stars whose removal disconnects the graph $G$ or leaves a single vertex or $\mathrm{\varnothing }$. This paper discusses the extreme values of the edge-neighbor-connectivity of graphs relative to the connectivity, $\kappa$, and gives two classes of graphs — one class with minimum edge-neighbor-connectivity, and the other one with maximum edge-neighbor-connectivity.