Z\(_3\)-CONNECTED GRAPHS WITH NEIGHBORHOOD UNIONS AND MINIMUM DEGREE CONDITION

Abstract

Let G be a 2-edge-connected simple graph on n ≥ 15 vertices, and let A denote an abelian group with the identity element 0.  If a graph G^* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G^*.  In this paper, we prove that if for every uv ∉ E(G), |N(u) ∪ N(v)| + δ(G) ≥ n, then G is not Z₃-connected if and only if G can be Z₃-reduced to one of {C₃, K₄, K\(_{4}^{-}\), L}, where L is obtained from K₄ by adding a new vertex which is joined to two vertices of K₄.  Our results extend the early theorem by Li et al. (Graphs and Combin., 29 (2013): 1891-1898).