On the λ′-optimality in graphs with odd girth g and even girth h

AbstractFor a connected graph G, the restricted edge-connectivity λ′(G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that there are no isolated vertices in G−S. A graph G is said to be λ′-optimal if λ′(G)=ξ(G), where ξ(G) is the minimum edge-degree in G defined as ξ(G)=min{d(u)+d(v)−2:uv∈E(G)}, d(u) denoting the degree of a vertex u. The main result of this paper is that graphs with odd girth g and finite even girth h≥g+3 of diameter at most h−4 are λ′-optimal. As a consequence polarity graphs are shown to be λ′-optimal