Let G be a graph and s 0 be an integer. If, for any function b : V ( G ) ? Z 2 s + 1 satisfying ? v ? V ( G ) b ( v ) ? 0 ( mod 2 s + 1 ) , G always has an orientation D such that the net outdegree at every vertex v is congruent to b ( v ) mod 2 s + 1 , then G is strongly Z 2 s + 1 -connected. For a graph G , denote by α ( G ) the cardinality of a maximum independent set of G . In this paper, we prove that for any integers s , t 0 and real numbers a , b with 0 < a < 1 , there exist an integer N ( a , b , s ) and a finite family Y ( a , b , s , t ) of non-strongly Z 2 s + 1 -connected graphs such that for any connected simple graph G with order n ? N ( a , b , s ) and α ( G ) ? t , if G satisfies one of the following conditions: (i)for any edge u v ? E ( G ) , max { d G ( u ) , d G ( v ) } ? a n + b , or(ii)for any u , v ? V ( G ) with d i s t G ( u , v ) = 2 , max { d G ( u ) , d G ( v ) } ? a n + b , then G is strongly Z 2 s + 1 -connected if and only if G is not contractible to a member in the finite family Y ( a , b , s , t ) .
['Aimei Yu', 'Jianping Liu', 'Miaomiao Han', 'Hong-Jian Lai']
On dense strongly Z 2 s + 1 -connected graphs