Inverse degree and super edge-connectivity

Abstract

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ _v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n−2δ)/(n−δ) (n−δ−1), then G is super edge-connected. We also give an analogous result for triangle-free graphs.

Keywords:

• edge-connectivity
• super edge-connectedness
• inverse degree
• optimization

AMS Subject Classification :

• 05C40

Acknowledgements

The research is supported by NSFC (No.10671165) and NSFXJ (No. 2010211A06).