On Z3-connectivity for graphs satisfying the Pósa-condition

Abstract

Let G be a simple graph on n ≥ 3 vertices and π ( G ) = ( d 1 , … , d n ) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . If d j ≥ j + 1 for each j with 1 ≤ j < ⌈ n − 1 2 ⌉ and d j + 1 ≥ j + 1 for n to be odd and j = n − 1 2 , then G satisfies the Pósa-condition . Zhang and Yin proved that if G satisfies the Pósa-condition and d 1 ≥ 3 and d 2 ≥ 4 , then G is Z 3 -connected. In this paper, we obtain a complementary result of Z 3 -connectivity for graphs satisfying the Pósa-condition. In other words, we show that if G is a simple graph on n ≥ 9 vertices with π ( G ) = ( d 1 , … , d n ) , and G satisfies the Pósa-condition and d ⌈ n − 4 2 ⌉ ≥ ⌈ n 2 ⌉ , then G is Z 3 -connected.