Restricted edge connectivity of graphs on degree

Abstract

Let G = (V, E) be a connected graph. An edge set S ⊂ E is a 3-restricted edge cut, if G - S is disconnected and every component of G - S has at least three vertices. The 3-restricted edge connectivity λ₃ (G) of G is the cardinality of a minimum restricted edge cut of G. A graph G is λ₃-connected, if 3-restricted edge cuts exist. A graph G is called λ′-optimal, if λ₃ (G) = ξ₃ (G), where ${\xi }_3\left(G\right)=min\left\{\right|[X,\overline{X}]|:X\subset V,|X|=3,G[X]$ is connected}. Furthermore, if every minimum 3-restricted edge cut is a set of edges incident to a set of three vertices, then G is said to be super 3-restricted edge connected or super-λ₃ for simplicity. Inverse degree of G is $R\left(G\right)={\sum }_{v\in V}\frac{1}{d\left(v\right)}$ , where d (v) denotes the degree of the vertex v. In this paper, we study the relation of inverse degree and super 3-restricted edge connected graphs.