Sufficient conditions for graphs to be super connected

GUO Litao

(School of Applied Mathematics， Xiamen University of Technology, Xiamen 361024,Fujian Province, China)

Abstract： Let G be a connected graph. 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. If every minimum vertex cut isolates a vertex of G, a graph G is super connected or super-κ. Define the inverse degree of a graph G with no isolated vertices as In this paper, we show that let G be a connected graph with order n and minimum degree δ， if then G is super-κ.

Key Words： connectivity; inverse degree; super connected

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.

LetG=(V,E) be a connected graph,dG(v) the degree of a vertexvinG(simplyd(v)), andδ(G) the minimum degree ofG. Moreover, forS?V,G[S] is the subgraph induced byS. AndG-Sdenotes the subgraph ofGinduced by the vertex set ofV,S. We writeKnfor the complete graph of ordern. Ifu,v∈V,d(u,v) denotes the length of a shortest (u,v)-path. And, the diameter isdm(G)=max{d(u,v):u,v∈V}.

The edge connectivityλ(G) of a connected graphGis the least positive integerksuch that there isF?E,|F|=kandG-Fis disconnected. A graphGis super edge connected or super-λ, if every minimum edge cut isolates a vertex ofG. IfGis super-λ, thenλ=δ. The connectivityκ(G) of a connected graphGis the least positive integerksuch that there isF?V,|F|=kandG-Fis disconnected or is a trivial graph. A graphGis super connected or super-κ, if every minimum vertex cut isolates a vertex ofG. IfGis super-κ, thenκ=δ. It is well known thatκ(G)≤λ(G)≤δ(G).

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

Theorem1A connected graphGwith ordernis super-λ, if one of the following conditions holds:

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

(2)d(u)+d(v)≥nfor all pairsu,vof nonadjacent vertices, andGis different fromKn/2×K2(by LESNIAK[3]);

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

(4)dm(G)=2, andGcontains no completeKδwith all its vertices of degreeδ(by FIOL[4]);

(5)Gis bipartite andd(u)+d(v)≥n/2+2 for all pairsu,vof vertices such thatd(u,v)≥3 (by FIOL[4]);

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

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.

(3) Iff(x) is continuous and convex on an interval [L,R], and ifl,r∈[L,R], withl+r=L+R, thenf(L)+f(R)≥f(l)+f(r).

(3) Follows from the definition of convex function.

Lemma2[10]LetGbe a connected graph of ordern, minimum degreeδ. If

thenκ=δ.

Theorem2LetGbe a connected graph with ordern, minimum degreeδ. If

thenGis super-κ.

ProofBy lemma 2,κ=δ. Suppose thatGis not super-κ. We assume thatS?V(G) with |S|=κis a cut ofG, andX1,X2,…,Xpare the connected components ofG-S. Then 2≤|Xi|≤n-δ(G)-2 fori=1,2,…,p.

Because every vertex ofSis adjacent to some vertex ofXifori=1,2,…,p. We can obtain

According to lemma 1, we have

Therefore, the inverse degree ofGis

Hence, we have

There is a contradiction.