0 Introduction

All graphs considered in this paper are simple, finite and undirected. Unless stated otherwise, we follow BONDY et al ^[1] for terminology and definitions.

Let G=(V, E) be a connected graph, d_G(v) the degree of a vertex v in G (simply d(v)), and δ(G) the minimum degree of G. Moreover, for S⊂V, G[S] is the subgraph induced by S. And G-S denotes the subgraph of G induced by the vertex set of V, S. We write K_n for the complete graph of order n. If u, v∈V, d(u, v) denotes the length of a shortest (u, v)-path. And, the diameter is dm(G)=max{d(u, v): u, v∈V}.

The edge connectivity λ(G) of a connected graph G is the least positive integer k such that there is F⊂E, |F|=k and G-F is disconnected. A graph G is super edge connected or super-λ, if every minimum edge cut isolates a vertex of G. If G is super-λ, then λ=δ. The connectivity κ(G) of a connected graph G is the least positive integer k such that there is F⊂V, |F|=k and G-F is disconnected or is a trivial graph. A graph G is super connected or super-κ, if every minimum vertex cut isolates a vertex of G. If G is super-κ, then κ=δ. It is well known that κ(G)≤λ(G)≤δ(G).

Different authors proposed sufficient conditions for a graph to be super-λ.

Theorem 1  A connected graph G with order n is super-λ, if one of the following conditions holds:

(1) δ≥(n+1)/2(by KELMANS ^[2]);

(2) d(u)+d(v)≥n for all pairs u, v of nonadjacent vertices, and G is different from K_n/2×K₂(by LESNIAK ^[3]);

(3) d(u)+d(v)≥n+1 for all pairs u, v of nonadjacent vertices(by LESNIAK ^[3]);

(4) dm(G)=2, and G contains no complete K_δ with all its vertices of degree δ(by FIOL ^[4]);

(5) G is bipartite and d(u)+d(v)≥n/2+2 for all pairs u, v of vertices such that d(u, v)≥3 (by FIOL^[4]);

(6) G is bipartite and δ≥max{3, (n+2)/4+1} (by FIOL^[4]);

(7) $R\left( G \right) < 2 + \frac{{n-2\delta }}{{\left( {n-\delta } \right)\left( {n-\delta - 1} \right)}}$(by TIAN et al^[5]).

Define the inverse degree of a graph G with no isolated vertices as $R\left( G \right) = \sum\limits_{v \in V} {\frac{1}{{d\left( v \right)}}} $.The inverse degree firstly attracted the attention through conjectures of the computer program^[6]. It has been studied by several authors ^[7-9]. In this paper, we show that let G be a connected graph with order n, minimum degree δ. If $R\left( G \right) < 1 + \frac{2}{{\delta + 1}} + \frac{{n-2\delta-1}}{{\left( {n-1} \right)\left( {n - 3} \right)}}$, then G is super-κ.

1 Main results

We start the section with the following useful lemmas.

The following lemmas can be found in [8], we rewrite its proof for convenience here.

Lemma 1 ^[8]  (1) Let a₁, a₂, …, a_p, A be positive deals with $\sum\limits_{i = 1}^p {{a_i} \leqslant A} $. Then $\sum\limits_{i = 1}^p {\left( {1/{a_i}} \right) \geqslant {p^2}/A} $.

(2) If, in addition a₁, a₂, …, a_p, A are positive integers, and a, b are integers with A=ap+b and 0≤b≤p, then $\sum\limits_{i = 1}^p {\left( {1/{a_i}} \right) \geqslant \left( {p-b} \right)/a + b/\left( {a + 1} \right)} $. Equality holds if and only if p-b of a_i equal to a and the remaining a_i equal to a+1.

(3) If f(x) is continuous and convex on an interval [L, R], and if l, r∈[L, R], with l+r=L+R, then f(L)+f(R)≥f(l)+f(r).

Proof  (1) Follows by applying the function $f\left( x \right) = \frac{1}{x}$, which is convex on the interval (0, ∞).

(3) Follows from the definition of convex function.

(2) We can assume that a_i are chosen such that $\sum {\frac{1}{{{a_i}}}} $ is minimum. If no two of the a_i differ by more than 1, then p-b of the a_i equals to a and the remaining b of the a_i equals to a+1, and the inequality follows. So assume that there are two of a_i, say a₁ and a₂, differ by more than 1: Assume further that a₁>a₂. Let b₁=a₁-1, b₂=a₂+1, and b_i=a_i for i≥3. Then we can find that $\sum {\frac{1}{{{a_i}}}} > \sum {\frac{1}{{{b_i}}}} $, a contradiction.

Lemma 2 ^[10]  Let G be a connected graph of order n, minimum degree δ. If

$ R\left( G \right) < 1 + \frac{2}{\delta } + \frac{{n-2\delta + 1}}{{\left( {n-1} \right)\left( {n-3} \right)}}, $

then κ=δ.

Theorem 2  Let G be a connected graph with order n, minimum degree δ. If

$ R\left( G \right) < 1 + \frac{2}{{\delta + 1}} + \frac{{n-2\delta-1}}{{\left( {n-1} \right)\left( {n - 3} \right)}}, $

then G is super-κ.

Proof  By lemma 2, κ=δ. Suppose that G is not super-κ. We assume that S⊂V(G) with |S|=κ is a cut of G, and X₁, X₂, …, X_p are the connected components of G-S. Then 2≤|X_i|≤n-δ(G)-2 for i=1, 2, …, p.

Because every vertex of S is adjacent to some vertex of X_i for i=1, 2, …, p. We can obtain

$ \sum\limits_{u \in {X_i}} {d\left( u \right)} \leqslant \left| {{X_i}} \right|\left( {\left| {{X_i}} \right|-1} \right) + \left| {{X_i}} \right|\delta = \left| {{X_i}} \right|\left( {\left| {{X_i}} \right| + \delta-1} \right). $

According to lemma 1, we have

$ \sum\limits_{u \in {X_i}} {\frac{1}{{d\left( u \right)}}} \geqslant \frac{{\left| {{X_i}} \right|}}{{\left| {{X_i}} \right| + \delta-1}}. $

For any vertex v∈S, d(v)≤n-1, thus $\sum\limits_{v \in S} {\frac{1}{{d\left( v \right)}}} \geqslant \frac{\delta }{{n-1}}$.Suppose that $X = \bigcup\limits_{i = 2}^p {{X_i}} $, then

$ \sum\limits_{i = 2}^p {\frac{{\left| {{X_i}} \right|}}{{\left| {{X_i}} \right| + \delta-1}} \geqslant \frac{{\left| X \right|}}{{\left| X \right| + \delta-1}}} . $

Therefore, the inverse degree of G is

$ \begin{gathered} R\left( G \right) \geqslant \sum\limits_{i = 1}^p {\frac{{\left| {{X_i}} \right|}}{{\left| {{X_i}} \right| + \delta-1}}} + \frac{\delta }{{n-1}} \geqslant \hfill \\ \frac{{\left| {{X_1}} \right|}}{{\left| {{X_1}} \right| + \delta-1}} + \frac{{\left| X \right|}}{{\left| X \right| + \delta - 1}} + \frac{\delta }{{n - 1}} = \hfill \\ 2 + \frac{\delta }{{n - 1}} - \left( {\delta - 1} \right)\left( {\frac{1}{{\left| {{X_1}} \right| + \delta - 1}} + \frac{1}{{\left| X \right| + \delta - 1}}} \right). \hfill \\ \end{gathered} $

We consider the function $g\left( t \right) = \frac{1}{{t + \delta-1}}$. It is easy to verify that g″(t)>0 for t>0, so g is convex. By |X₁|, |Y|≥2, |X₁|+|Y|=n-δ and applying lemma 1 (3) to the function g(t), we get

$ \frac{1}{{\left| {{X_1}} \right| + \delta-1}} + \frac{1}{{\left| X \right| + \delta-1}} \leqslant \frac{1}{\delta } + \frac{1}{{n-2}}. $

Hence, we have

$ \begin{gathered} R\left( G \right) \geqslant 2 + \frac{\delta }{{n-1}} + \left( {\delta-1} \right)\left( {\frac{1}{\delta } + \frac{1}{{n-2}}} \right) = \hfill \\ \;\;\;\;\;\;\;\;\;\;1 + \frac{2}{{\delta + 1}} + \frac{{n - 2\delta - 1}}{{\left( {n - 1} \right)\left( {n - 3} \right)}}. \hfill \\ \end{gathered} $

There is a contradiction.