On the g-extra connectivity of graphs

In 1996, Fàbrega and Fiol introduced the g-extra connectivity of G as an important parameter for the fault tolerance of an interconnection network. A subset of vertices S is said to be a cutset if G−S is not connected. A cutset S is called an R_g-cutset, where g is a non-negative integer, if every component of G−S has at least g+1 vertices. If G has at least one R_g-cutset, the g-extra connectivity of G, denoted by κ_g(G), is then defined as the minimum cardinality over all R_g-cutsets of G. In this paper, we obtain the exact values of the g-extra connectivity of some special graph classes, and show that 1≤κ_g(G)≤n−2g−2 for [Formula presented], and graphs with κ_g(G)=1,2,3 and trees with κ_g(T_n)=n−2g−2 are characterized, respectively. We also derive three extremal results for the g-extra connectivity.