/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 35-47
^-connectivity of K 1,3-free graphs without induced cycle of length at least 5
Xiangwen Li, Jianqing Ma
Department of Mathematics, Huazhong Normal University, Wuhan 430079, China
Received 26 September 2014, accepted 2 June 2015, published online 18 August 2015
Abstract
Jaeger et al. conjectured that every 5-edge-connected graph is Z3-connected. In this paper, we prove that every 4-edge-connected K1j3-free graph without any induced cycle of length at least 5 is Z3-connected, which partially generalizes the earlier results of Lai [Graphs and Combin. 16 (2000) 165-176] and Fukunaga [Graphs and Combin. 27 (2011) 647-659].
Keywords: Z3-connectivity, Kli3-free, nowhere-zero 3-flow. Math. Subj. Class.: 05C40
1 Introduction
Graphs in this paper are finite, loopless, and may have multiple edges. Terminology and notations not defined here are from [1].
For a graph G and v e V(G), denote by NG(v) (or shortly N(v)) the set of neighbors of v in G. Let dG(v) = |NG(v)| and N[v] = N(v) U {v}. For A c V(G), let N(A) = UveAN(v) \ A. A graph G is trivial if |V(G)| = 1, and non-trivial otherwise. An n-cycle is a cycle of length n. A path Pn is a path on n vertices. The complete graph on n vertices is denoted by Kn, and K- is obtained from Kn by deleting an edge. For two vertex-disjoint subgraphs H1 and H2 of G, denote by eG(H1, H2) (or simply e(H1; H2)) the number of edges with one end vertex in H1 and the other one in H2. If V(H1) = {a}, we use eG(a, H2)(or simply e(a, H2)) instead of eG(H1? H2). For simplicity, if V1, V2 are two disjoint subsets of V(G), we use eG(V1, V2) for eG(G[V1], G[V2]). Similarly, we define e(V1, V2) and e(a, V2). For graphs H1,..., Hs, a graph G is {H1,..., Hs}-free if for each i e {1,2,..., s}, G has no induced subgraph Hj.
E-mail addresses: xwli68@mail.ccnu.edu.cn (Xiangwen Li), binger728@163.com (Jianqing Ma)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
36
Ars Math. Contemp. 11 (2016) 35-47
Let G be a graph and let D be an orientation of G. If an edge e = uv G E (G) is directed from a vertex u to a vertex v, then u is a tail of e, v is a head of e. For a vertex v G V(G), let E+ (v)={e G E(D): v is a tail of e }, and E-(v)={e G E(D): v is a head of e }. Let A be an abelian group with identity 0 and A* = A - {o}. Define F(G, A) = {f : E(G) ^ A} and F*(G, A) = {f : E(G) ^ A*}. For each f G F(G, A), the boundary of f is a function df : V(G) ^ A given by,
where "J2" refers to the addition in A.
Afunction b : V (G) ^ A iscalledan A-valued zero-sum function on G if^„eV (G)b(v) = 0. The set of all A-valued zero-sum functions on G is denoted by Z(G, A). A graph G is A-connected if G has an orientation D such that for any b G Z(G, A), there is a function f G F(G, A*) such that df (v) = b. In particular, if df (v) = 0 for each vertex v G V(G), then f is called a nowhere-zero A-flow of G. More specifically, a nowhere-zero k-flow is a nowhere-zero Zk-flow, where Zk is the cyclic group of order k. Tutte [16] proved that G admits a nowhere-zero A-flow with | A | = k if and only if G admits a nowhere-zero k-flow.
Integer flow problems were introduced by Tutte in [16]. Group connectivity was introduced by Jaeger et al. in [7] as a generalization of nowhere-zero flows. The following longstanding conjecture is due to Jaeger et al. and is still open.
Conjecture 1.1. (Jaeger et al. [7]) Every 5-edge-connected graph is Z3-connected.
Conjecture 1.1 was extensively studied over thirty years. For the literature, some results can be seen in [3,4, 10, 13, 17, 18] and so on. Recently, Thomassen [15] proved that every 8-edge-connected graph is Z3-connected, which improved by Lovasz, Thomassen, Wu and Zhang [12] as follows.
Theorem 1.2. Every 6-edge-connected graph is Z3-connected.
However, Conjectures 1.1 is still open. A graph is chordal if every cycle of length at least 4 has a chord. A graph G is bridged if every cycle C of length at least 4 has two vertices x,y such that dG(x,y) < dC (x, y). A graph is HHD-free if any k-cycle for k > 5 in the graph has at least two chords. Lai [9] characterized Z3-connectivity of 3-edge-connected chordal graphs. Li et al. [11] and Fukunaga [6] generalized this result to bridged graphs and 4-edge-connected HHD-free graphs.
Theorem 1.3. (Fukunaga[6]) Every 4-edge-connected HHD-free graph is Z3-connected.
df (v)= ^ f (e)	f (e),
eEE+ (v)	eEE-(v)
w
x -iy	-
house	domino
Figure 1: 2 forbidden graphs
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
37
On the other hand, it is easy to see that a graph G is HHD-free if and only if G contains no induced subgraph isomorphic to house, domino and k-cycle where k > 5. Note that a domino contains a K13 as a subgraph. One naturally ask whether both house and domino may be replaced by a K1j3. On the other hand, Xu [14] proved that Conjecture 1.1 is true if and only if every 5-edge-connected K1j3-free graph is Z3-connected. Thus, we consider Z3-connectivity of K1j3-free graphs without induced cycle of length at least 5 and prove the following theorem in this paper.
Theorem 1.4. Let G be a 4-edge-connected, K13-free simple graph. If G does not contain any induced cycle of length at least 5, then G is Z3-connected.
Theorem 1.4 cannot be implied by Theorem 1.2 in the sense that there are infinite graphs which is Z3-connected by Theorem 1.4 but not by Theorem 1.2 as follows. Let H1 be a copy of K5 and H2 be a copy of Km where m > 5. Pick a vertex u of H1 and a vertex v of H2. Define Gm to be the graph obtained from H1 and H2 by identifying u and v. It is easy to see that for each m > 5, Gm is a 4-edge-connected K1j3-free graph without any induced cycle of length at least 5. Thus, Gm is Z3-connected by Theorem 1.4. Clearly, Gm has an edge cut of size 4 which implies Theorem 1.2 does not show that Gm is Z3-connected.
Theorem 1.3 cannot imply Theorem 1.4 in the sense that there are infinite graphs which is Z3-connected by Theorem 1.4 but not by Theorem 1.3 as follows. Let Hj be a copy of Kni where 1 < i < 4 and nj > 5 for i e {1,2,3,4}. Pick two distinct vertices uj and vj of Hj. Denote by rn the graph obtained from H1, H2, H3, H4 by identifying vj with uj+1 for i = 1, 2, 3, and v4 with u1. It is easy to verify that rn contains a house and so Theorem 1.3 cannot guarantee that rn is Z3-connected but Theorem 1.4 does.
The paper is organized as follows: In Section 2, the former related results are presented, and some lemmas are established. In Section 3, the main theorem is proved.
2 Lemmas
For a subset X C E(G), the contraction G/X denotes the graph obtained from G by identifying the two ends of each edge in X and then deleting all the resulting loops. Note that even if G is simple, G/X may have multiple edges. For convenience, we write G/e for G/{e}, where e e E(G). If H is a subgraph of G, then we write G/H for G/E(H).
For k > 2, a wheel Wk is the graph obtained from a k-cycle by adding a new vertex, called the center of the wheel, which is adjacent to every vertex of the k-cycle. A wheel Wk is odd (even) if k is odd (or even). For technical reasons, we refer the wheel W1 to a 3-cycle.
In order to prove Theorem 1.4, we need some lemmas. Some results [2, 5, 7, 8, 9, 10] on group connectivity are summarized as follows.
Lemma 2.1. Let A be an abelian group and G a simple graph. Then each of the following holds:
(1)	K1 is Z3-connected.
(2)	If e e E(G) and if G is A-connected, then G/e is A-connected.
(3)	If H is a subgraph of G and if both H and G/H are A-connected, then G is A-connected.
(4)	For n > 5, K- and Kn are Z3-connected;
(5)	An n-cycle is A-connected if and only if | A| > n +1;
38
Ars Math. Contemp. 11 (2016) 35-47
(6)	For every positive integer k, W2k is Z3-connected and W2k+1 is not Z3-connected.
(7)	Let H be a Z3-connected subgraph of G. If e(v, V(H)) > 2 for v G V(G — H), then the subgraph induced by V(H) U {v} is Z3-connected.
(8)	Let H1, H2 be subgraphs of G such that H1 and H2 are A-connected, If V(H1) n V(H2) = 0, then H1 U H2 is A-connected.
For a graph G with u, v, w G V(G) such that uv, uw G E(G), let G[„v,„w] denote the graph obtained from G by deleting two edges uv and uw, and then adding a new edge vw,
that is, G[„v „w] = G U {vw} — {uv, uw}.
Lemma 2.2. (Chen et al. and Lai, [2, 9]) Let A be an abelian group, let G be a graph
and u, v, w be three vertices of G such that d(u) > 4 and v, w G N(u). If G[„v,„w] is A-connected, then so is G.
A graph G satisfies the Ore-condition if dG(w) + dG(v) > n for every pair of nonadja-cent vertices u and v of G.
Theorem 2.3. (Luo et al. [13]) Let G be a simple graph on n vertices, where n > 3. If G satisfies the Ore-condition, then G is not Z3-connected if and only if G is one of {G1, G2,..., G12} shown in Figure 2.

G2
G8	G9
Xi
G
10
G11 Xi
G
i2
G13	G14
Figure 2: 14 specified graphs
Lemma 2.4. Suppose that H is one graph of {G7, G13, G14}. Denote by G the graph obtained from H by adding an edge e = xy which is neither of H nor parallel to any existing edge of H. Then G is Z3-connected.
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
39
Proof. We use the same notation of G13, G14 shown in Figure 2. Let H = G7, then G satisfies the Ore-condition. By Theorem 2.3, G is Z3-connected.
Let H = G13. If x2 G {x, y}, then G satisfies the Ore-condition. By Theorem 2.3, G is Z3-connected. Thus, assume that x2 G {x, y}. By symmetry, let e = x1x5. Contracting 2-cycle in G[XlX2,XlX3] and contracting all 2-cycles generated in the process, we get an even wheel W4 with the center at x5, which is Z3-connected by Lemma 2.1 (6) and so G is Z3-connected by Lemma 2.2.
Let H = G14. If e = x2x8, then G satisfies the Ore-condition. Since |V(H)| = 8, by Lemma 2.3, G is Z3-connected. Thus, assume that e = x2x8. By symmetry, assume that e = x1x5 or e = x2x6. In the former case, contracting 2-cycle in G[XlX2,XlX3] and contracting all 2-cycles generated in the process, we obtain an even wheel W4 induced by {x1, x4, x5, x6,x7} with the center at x5. Contracting this W4 into one vertex and contracting 2-cycle generated in the process, finally we get a K1 which is Z3-connected. By Lemmas 2.1 (7) and 2.2, G is Z3-connected. In the latter case, contracting 2-cycle in G[XlX2,XlX3] and contracting all 2-cycles generated in the process, we obtain an even wheel W4 induced by {x4, x5, x6, x7, x8} with the center at x5, which is Z3-connected by Lemma 2.1. Note that x1 has two neighbors in this even wheel. By Lemma 2.1(7), G[XlX2,XlX3] is Z3-connected. By Lemma 2.2, G is Z3-connected.	□
3 Proof of Theorem 1.4
Throughout this section, we assume that k'(G) > 4, K1j3-free simple graph and G does not contain any induced cycle of length at least 5. We argue our proof by contradiction, assume that G is a counterexample to Theorem 1.4 with | V(G) | minimized.
Lemma 3.1. Suppose that H is amaximal Z3-connected subgraph of G and Hi is a component of G - V(H). Let x1 G V(H) such that x1y1,..., x1yk, where y1,..., yk G V(Hi) and 2 < k < 3. Then each of y1,..., yk is not a cut vertex of Hi.
Proof. We only prove the case that k = 3. The proof for that k = 2 is similar. Without loss of generality, we will prove that y3 is a cut vertex of Hi. Suppose otherwise that y3 is not a cut vertex of Hi. Since the maximality of H, e(yi, H) = 1 by Lemma 2.1 (7). Since G
is K1,3-free, y1y2, y1y3, y2y3 G E(G). Since k'(G) > 4, let x4 g V(H) and y4 G V(Hi) such that x4y4 G E(G), and y4 is not in the component of Hi - y3 containing y1 and y2.
Consider the neighbors of y1 and y2. Let N(y1) \ {x1, y2, y3} = {u1, u2,...,ua} and N(y2) \ {x1,y1,y3} = {v1,v2,... , vb}. Since G is K1j3-free, both subgraphs induced by {u1,..., ua} and by {v1,..., vb} are complete graphs. We assume, without loss of generality, that a > b. Since G is 4-edge-connected, a > 1 and b > 1. Note that y3 is a cut vertex of Hi and G is K13-free. The following claim is straightforward.
Claim. All neighbors of y3 are y1, y2 in the component of Hi - y3 containing {y1, y2}. Case 1. {«1,..., ua} n {v1, V2,..., v6} = 0.
If a > 4, then the subgraph induced by {y1, u1, u2,..., ua} is a complete graph Ka+1, which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U {y1, y2, y3, u1, u2,..., ua}, contrary to the maximality of H. Thus, a < 3.
40
Ars Math. Contemp. 11 (2016) 35-47
Assume that a = 3. If |{«i, w2,..., ua} n jvi, v2,..., vb}| > 2, then the subgraph induced by {y1, y2, u1,..., ua} is K5 or K—, which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H)U{y1, y2, y3, u1, w2, ..., ua} which is larger than H, contrary to the choice of H. Thus, |{u1, w2,..., ua} n {v1, v2,..., vb}| = 1 and let u1 = v1. Assume that 3 > b > 2. Since k'(G) > 4, there is a path from {w2, w3} to v2 avoiding each vertex of {y1, y2, u1}. Since G contains no induced cycle of length at least 5, ujv2 G E(G) where i G {2, 3}. In this case, G contains an even wheel W4 induced by {y1, y2, u1, Wj, v2} with the center at u1, which is Z3-connected by Lemma 2.1 (6). By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U {y1, y2, y3, u1, u2,..., ua}, contrary to the maximality of H. Thus, b = 1. In this case, since k'(G) > 4, let u2p1, u3q1 G E(G) where p1 G {u1,u3,y1} and q1 G {u1,u2,y1}. Since k'(G) > 4 and G contains no cycle of length at least 5, p1q1,p1u3, q1u2 G E(G). We replace p1 with w2 and replace q1 with w3. By argument above, we obtain p2, q2 such that p2q2,p2p1, q2q1,p2q1, q2p1 G E(G). Repeating such a way, we can obtain two infinite sequences of p1,p2,... and q - 1, q2... such that PiPi+1, qiqi+1,Piqi,Piqi+1,qi, qi+1 G E(G) for i = 1,2,.... This contradicts that G is finite.
We are left to consider that a < 2. In this case, since G is 4-edge-connected, a = b = 2 and {u1, w2} = {v1, v2}. As the proof above, we also obtain a contradiction.
Case 2. {«1,..., wa} n {v1, v2,..., v6} = 0.
We claim that a + b > 4. Suppose otherwise that a + b < 3. It follows that either a = 2, b =1 or a = b =1. We only prove the case when a = 2 and b = 1. The proof is similar for the case that a = b =1. Since a = 2 and b =1, y1u1, y1u2, y2v1 G E(G). By the Claim, y3 is not adjacent to one of u1, w2 and v1. Thus, {y1u1, y1u2, y2v1} is an edge cut of size 3, contrary to that k'(G) > 4.
Assume that a > 4. If b > 4, then G contains a path from {u1,..., ua} to {v1,..., vb}. Note that k'(G) > 4 and G has no cycle of length at least 5. If 2 < b < 3, then each vertex of {v1, v2..., vb} has a neighbor in {u1, w2, ..., ua}. If b = 1, then v1 has three neighbors in {u1,..., ua}. By Lemma 2.1 (4), G contains a Z3-connected subgraph Ka+1. By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U {y1, y2, y3, u1,..., ua, v1,..., vb}, contrary to the maximality of H.
Assume that a = 3. If b = 3, denote by F the subgraph induced by {u1, w2, w3, v1, v2, v3, y1, y2}. Since k'(G) > 4 and G contains no cycle of length at least 5, each vertex of {u1, u2, u3} is adjacent to one of {v1, v2, v3} and each vertex of {v1, v2, v3} is adjacent to each vertex of {u1,u2,u3}. Since k'(G) > 4, e({«1, w2, w3}, {v1,v2,v3}) > 3 and each vertex of F is of degree 4 and this subgraph satisfies the Ore-condition. By Theorem 2.3, F is Z3-connected. By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V (H) U V (F), contrary to the maximality of H.
Let b = 2. Since k'(G) > 4 and G contains no cycle of length at least 5, each vertex of {u1, w2, w3} is adjacent to one of {v1, v2} and each vertex of {v1, v2} is adjacent to two vertices of {u1, w2, w3}. It follows that one, say w3, of {u1, w2, w3} has two neighbors in {v1, v2}. It implies that the subgraph induced by {u1, u2, u3, v1, v2} is an even wheel W4 with the center at w3, which is Z3-connected by Lemma 2.1 (6). By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U {y1, y2, y3, u1, w2, w3, v1, v2}, contrary to the maximality of H.
Let b = 1. Since k'(G) > 4 and G contains no cycle of length at least 5, v1 is adja-
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
41
cent to each vertex of {wi, w2, w3}. The subgraph induced by {ui, , «3, v1, yi} is K—, which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U {y1, y2, y3, u1, u2, u3, v1}, contrary to the maximality of H.
Next, assume that a = 2. Let b = 2. Since k'(G) > 4 and G contains no cycle of length at least 5, each vertex of {u1, w2} is adjacent to two of {v1, v2} and each vertex of {v1, v2} is adjacent to two vertices of {u1, u2}. Denote by F the subgraph induced by {y1,y2,u1,u2, v1, v2}. It follows that F satisfies the Ore-condition and each of 4 vertices of F is of degree 4. By Theorem 2.3, F is Z3-connected. By Lemma 2.1 (7), G contains a Z3-connected subgraph induced by V(H) U V(F), contrary to the maximality of H. □
Lemma 3.2. G does not contain a nontrivial Z3-connected subgraph H.
Proof. Suppose that our lemma fails and H is a maximal Z3-connected subgraph of G. Supposethat H1,H2,...,Hk are components of G - V(H), where k > 1. Let G = G/H and v be the vertex into which H is contracted.
Observe H,, where i G {1,2,..., k}. Let E(H, H,) = {x1y1, x2y2,..., xtyt}, where xi G V(H) and yj G V(H,) for i, j G {1, 2,..., t}. Since G is 4-edge-connected, t > 4. By the maximality and by Lemma 2.1 (7), y1,..., yt are distinct t vertices of H,. Let e, = x,yi for i G {1, 2,... ,t}.
Claim 1. E(H, H,) does not contain 4 edges having a common end-vertex.
Proof of Claim 1. Suppose otherwise that without loss of generality, that e1, e2, e3, e4 have a common vertex x1, that is, x1 = x2 = ... = x4. Then the subgraph induced by {x1, y1,..., y4} is a complete graph K5 since G is K1j3-free. By Lemma 2.1 (4), K5 is Z3-connected. By Lemma 2.1 (8), G contains a Z3-connected subgraph induced by V(H) U {x1, y1,..., y4}, contrary to the choice of H. Thus, E(H, H,) contains at most three edges having a common vertex. This proves Claim 1.
Claim 2. E(H, H,) does not contain 4 independent edges.
Proof of Claim 2. Suppose otherwise that E (H, H,) contains 4 independent edges. We assume,without loss of generality, that e1, e2, e3, e4 are independent edges. Since G has no induced cycle of length at least 5, as the argument above, y,yj G E(G) for 1 < i < j < 4. This means that the subgraph the subgraph induced by {y1, y2,y3, y4} is a K4. In the graph G', the subgraph induced by {v', y1, y2, y3, y4} is a K5 which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (3), the subgraph induced by V(H) U {y1, y2, y3, y4} is Z3-connected, contrary the maximality of H. This proves Claim 2.
Claim 3. E(H, H,) does not contain 2 edges having a common end-vertex.
Proof of Claim 3. By Claim 2, we assume that t = 4 and e1, e2, e3, e4 have at least a pair of two edges sharing a vertex in H. Suppose otherwise that we assume, without loss of generality, that e1, e2 have a common vertex x1, that is, x1 = x2. Since t = 4, we need to consider e3 and e4 do not share a common end-vertex or e3 and e4 share a common end-vertex.
In the former case, the subgraph induced by {x1, y1, y2} is a K3 since G is K1j3-free. Since G has no induced cycle of length at least 5, y3y4 G E(G), y3y,,y4yj G E(G) where i, j G {1,2}. By Lemma 3.1, the subgraph induced by {y1, y2, y3, y4} is a K4 since G has no induced cycle of length at least 5. In the graph G', the subgraph induced by {v', y1, y2, y3, y4} is a K5 which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (3),
42
Ars Math. Contemp. 11 (2016) 35-47
the subgraph induced by V(H) U {y^ y2, y3, y4} is Z3-connected, contrary the choice of H.
In the latter case, we assume, without loss of generality, that e3 and e4 share a common end-vertex x3. Since G is Kij3-free, the subgraph induced by {xi, yi, y2} is a complete graph and so is the subgraph induced by {x3, y3, y4}. Since G has no induced cycle of length at least 5, as the argument above, y^ G E(G) for some i G {1,2} and some j G {3,4}. We assume, without loss of generality, that i = 2, j = 3. By Lemma 3.1, each vertex of {yi, y2, y3, y4} is not a cut vertex. Since G has no induced cycle of length at least 5 and G is 4-edge-connected, y2 is adjacent to y4, and y3 is adjacent to yi. In the graph G', the subgraph induced by {v', yi, y2, y3, y4} is a K- which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (3), the subgraph induced by V(H) U {yi, y2, y3, y4} is Z3-connected, contrary the maximality of H. This proves Claim 3.
By Claims 1, 2, and 3, we assume, without loss of generality, that ei, e2, e3 have a common vertex xi, that is, xi = x2 = x3. Thus, t = 4 and x4 = xi. It follows that the subgraph induced by {xi, yi, y2, y3} is a complete graph K4. Consider the cycle xiPx4y4Qyj, where V(P) c V(H), V(Q) c V(Hi) and j G {1,2, 3}. Since G contains no any induced cycle of length at least 5, V(P) = V(Q) = 0 and xix4, y4yj G E(G). We assume, without loss of generality, that j = 3, that is, y3y4 G E(G). By Lemma 3.1, each of {yi, y2, y3} is not cut vertex. Since G contains no any induced cycle of length at least 5 and k'(G) > 4, yiy4, y2y4 G E(G). This, in the graph G', the subgraph induced by {v', yi, y2, y3, y5} is a K5, which is Z3-connected by Lemma 2.1 (4). By Lemma 2.1 (3), the subgraph induced by V(H) U {yi, y2, y3, y4} is Z3-connected, contrary the maximality of H.	□
Proof of Theorem 1.4
Since domino contains an induced Ki 3 and G contains no induced Ki 3, G contains no induced domino. By Theorem 1.3 and the choice of G, G contains an induced house. We use the same notations depicted in Figure 2. By symmetry, assume that d(u) < d(v).
Claim 1. |N(u) n N(v) \ {w}| < 1.
Proof of Claim 1. Suppose otherwise that |N(u) n N(v) \ {w}| > 2. Let ui, vi G N(u) n N(v) \ {w}. Denote by F the subgraph induced by {ui, vi, w}. Since G is Kij3-free, F contains at least one edge. If F contains two edges, then the subgraph induced by {ui, vi, w, u, v} contains an even wheel W4, which is Z3-connected by Lemma 2.1 (6), contrary to Lemma 3.2. Thus, F contains only one edge e. By symmetry, assume that e = wui or e = uivi. In each case, since G is Kij3-free, xvi, yvi G E(G). This means that the subgraph induced by {vi, u, v, x, y} is an even wheel W4 with the center at vi, which is Z3-connected by Lemma 2.1 (6), contrary to Lemma 3.2. This proves Claim 1.
Claim 2. |N(u) n N(v) \ {w}| = 0.
Proof of Claim 2. Suppose otherwise that |N (u) n N (v) \ {w}| = 0. Since k' (G) > 4, ¿(G) > 4. First, we claim that max{d(u), d(v)} < 5. Suppose otherwise that d(u) > 6. Let ui,u2,u3 G N(u) \ {w, v, x}. Since G is Kij3-free, either G[{u, x, ui, u2, u3}] or G[{u, w, ui, u2, u3}] is a complete subgraph K5 which is Z3-connected by Lemma 2.1, contrary to Lemma 3.2. Thus, 4 < d(u), d(v) < 5.
Assume first that d(u) = d(v) = 4. Let N(u) \ {w,v,x} = {ui} and N(v) \ {w,u,y} = {vi}. Since G is Ki 3-free and uiv,viu G E(G)), uix, viy G E(G).
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
43
Since G contains no induced cycle of length at least 5 and k'(G) > 4, uivi G E(G). If u1y G E(G) or xv1 G E(G), then G[{u, v,u1, v1,x, y}] contains a subgraph isomorphic to G7 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, assume that u1 y, xv1 G E(G). Since G contains no induced cycle of length at least 5, wv1,wu1 G E(G). Since k'(G) > 4, there exists a shortest (u1 , w)-path P such that NP(u1) G {u, x, v1}. Since wu1 G E(G), u2 G V(P) such that u^2,u2w g E(G) since G contains no induced cycle of length at least 5. Consider the cycle wu2^xyvw. Since G contains no induced cycle of length at least 5, u2y, u2x G E(G). Since |N(u) n N(v) \ {w}| = 0, u2v G E(G). This implies that G contains a K1j3 induced by {u2, u1, w, y}, a contradiction.
Next, assume that d(u) = 4 and d(v) = 5. Let N(u) \ {w, v,x} = {u1} and N(v) \ {w,v,y} = {v1, v2}. Since G is K1j3-free and |N(u) n N(v) \ {w}| = 0, u1x, v1y, v2y, v1v2 G E(G). If wv1,wv2 G E(G), then G contains a induced by {w, v, v1, v2, y} which is Z3-connected by Lemma 2.1 (4), contrary to Lemma 3.2. Thus, assume that wv1 G E(G). Since G contains no induced cycle of length at least 5 and k'(G) > 4, u1 v1 G E(G). If u1y G E(G) or u1v2 G E(G), then G[{u, v, x, y, u1, v1, v2}] contains a subgraph isomorphic to G13 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, assume that u1 y, u1v2 G E(G). As the proof above, there is u2 such that such that u1u2, u2w G E(G) and u2y, u2x G E(G). It follows that G contains a K1j3 induced by {u2, u1, w, y}, a contradiction.
Finally, assume that d(u) = d(v) = 5. Let N(u) \ {w, v,x} = {u1,u2} and N(v) \ {w,u,y} = {v1 ,v2}. SinceGis K13-freeand |N(u)nN(v)\{w}| = 0,u1x,u2x,u1u2, v1y, v2y, v1v2, u1v1 G E(G). If {u2y, u2v2, u2v1}nE(G) = 0, then G[{u, v, x, y, u1, u2, v1, v2}] contains a subgraph isomorphic to G14 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, assume that u2y, u2v2, u2v1 G E(G). Since G contains no induced cycle of length at least 5, u2w G E(G). Since k'(G) > 4, as the proof above, there exists a vertex u3 g V(P) such that u2u3, u3w G E(G) and u3x, u3y G E(G). In this case, G contains a K13 induced by {u3, u2, y, w}, a contradiction. This proves Claim 2.
By Claims 1 and 2, assume that N(u) n N(v) \ {w} = {z}. If xz,yz G E(G), then G[{u, v, x, y, z}] is a Z3-connected subgraph W4, contrary to Lemma 3.2. Thus, xz G E(G) or yz G E(G). Recall that d(u) < d(v). We claim that d(v) < 6. Otherwise, since G is K1j3-free, G[N[v] \ {w, u, z}] contains a complete subgraph Km, where m > 5, which is Z3-connected by Lemma 2.1, contrary to Lemma 3.2. Thus, 4 < d(u), d(v) < 6.
Case 1. xz, yz G E(G).
Since G[{u, w, x, z}] is not an induced K13, wz G E(G). We first establish a claim.
Claim 3. If d(u) = 4, then d(x) = 4; if d(v) = 4, then d(y) = 4.
Proof of Claim 3. Suppose otherwise that d(x) > 5. Since d(u) = 4, each s G N(x) \ {u} is not adjacent to u. Thus, G[N[x] \ {u}] is a Z3-connected Km, where m > 5, since G is K1j3-free, contrary to Lemma 3.2. Since G is 4-edge-connected, d(x) > 4. Thus, d(x) = 4. The proof for the case that d(y) = 4 is similar. This proves Claim 3.
Assume that d(u) = d(v) = 4. By Claim 3, d(x) = 4. Let N(x) \ {u, y} = {x1, x2}. Since G is K1j3-free, yx1,yx2,x1x2 G E(G). Since k'(G) > 4, G contains a path from x1 to w which does not contains any vertex of {x2, x, y, u, v}. Since G contains no induced cycle of length at least 5, this path is an edge, that is, x1w g E(G) or x1z g E(G). Similarly, we can prove that x2z G E(G) or x2w G E(G). In each case, H =
44
Ars Math. Contemp. 11 (2016) 35-47
G[{u, v, x, y, x1, x2, w, z}] satisfies the Ore-condition. By Lemma 2.3, H is Z3-connected, contrary to Lemma 3.2.
Assume that d(u) = 4 and d(v) = 5. Let N(v) \ {u, w, z,y} = {v1}. Since G is K1j3-free, yv1 G E(G). By the Claim, d(x) = 4. Assume that xv1 G E(G). Let xx1 G E(G). Since G is K1j3-free, x1y, x1v1 G E(G). Let H = G[{u, v, x, y, x1, v1, w, z}]. If wv1 G E(G), contract the 2-cycle (v, v1) in H[wv,wvi j and repeatedly contact the 2-cycles generated in the process, eventually, we get a K1 which is Z3-connected. By Lemmas 2.1 and 2.2, H is Z3-connected, contrary to Lemma 3.2. Thus, wv1 G E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, x1w g E(G). As the proof above, we can get H[xiy xivi] is Z3-connected. By Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2.
Thus, xv1 G E(G). Let xx1 ,xx2 G E(G). Since G is K13-free, yx1,yx2,x1x2 G E(G). Since G contains no induced cycle of length at least 5, x1v1, x2v1, wv1, zv1 G E(G). Since G contains no induced cycle of length at least 5 and k'(G) > 4, x1w, x2z G E(G) or x1z, x2w G E(G). In each case, L = G[{u, v,x, y, x1,x2, w, z}] satisfies the Ore-condition. By Lemma 2.3, L is Z3-connected, contrary to Lemma 3.2.
If d(u) = 4 and d(v) = 6, let N(v) \ {u, w, z, y} = {v1, v2}. Since G is K13-free, v1y,v2y,v1v2 G E(G). By the Claim, d(x) = 4. First assume that xv1,xv2 G E(G). In this case, G contains a Z3-connected subgraph K- induced by {x, y, v, v1, v2}, contrary to Lemma 3.2. Next, assume that xv1 G E(G) and xv2 G E(G). Let xx1 G E(G). Since G is K1j3-free, x1y, x1v1 G E(G). Let H = G[{w, u, v,x, y, x1, v1, v2}]. If wv1 G E(G) or wv2 G E(G) or x1z G E(G), we can prove that H[wv,wvi] or H[wv,wv2] or H[xiy,xivi] is Z3-connected. By Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2. If x1 v2 G E(G), then G contains a Z3-connected subgraph K- induced by {x1, y, v, v1, v2}, a contradiction. Thus, wv1, wv2, x1z, x1v2 G E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, wx1 G E(G). As the argument above, H[xiy xivi] is Z3-connected. By Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2. Finally, assume that xv1, xv2 G E(G). Let xx1, xx2 G E(G). Since G is K1j3-free, x1x2, yx1, yx2 G E(G). Since G contains no induced cycle of length at least 5, wv1, wv2, zv1, zv2 G E(G) and e({x1,x2}, {v1,v2}) = 0. Since k'(G) > 4 and G contains no induced cycle of length at least 5, wx1, zx2 G E(G) or wx2, zx1 G E(G). In each case, L = G[{w, u, v, x, y, x1, x2, z}] satisfies the Ore-condition, by Lemma 2.3, L is Z3-connected, contrary to Lemma 3.2.
If d(u) = 5 and d(v) = 5, let N(u) \ {v, w, z, x} = {u1} and N(v) \ {u, w, z, y} = {v1}. Since G is K1j3-free, u1x, v1y G E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, u1v1 G E(G). If u1y G E(G) or v1x G E(G), then G[{u,v,x,y,u1,v1}] contains a subgraph isomorphic to G7 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, u1y, v1x G E(G). Assume that u1z G E(G). Since G is K1j3-free, v1z G E(G). It follows that G contains a Z3-connected subgraph W4 induced by {u, v, u1, v1, z} with the center at z, contrary to Lemma 3.2. Thus, by symmetry, we assume that u1z, v1z G E(G) and wu1, wv1 G E(G). As k'(G) > 4, there is w1 such that u1w1, w1w G E(G). Observe cycle ww1u1xyvw. Since G contains no induced cycle of length at least 5, w1y G E(G). It follows that G contains a K13 induced by {w1, u1, w, y}, a contradiction.
If d(u) = 5 and d(v) = 6, let N(u) \ {v, w, z, x} = {u1} and N(v) \ {u, w, z, y} = {v1, v2}. Since G is K1j3-free, u1x, v1y, v2y, v1v2 G E(G). Since G contains no induced cycle of length at least 5, wv1, wv2, zv1, zv2 G E(G). Since k'(G) > 4 and G contains
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
45
no induced cycle of length at least 5, by symmetry, we assume that uivi G E(G). If {uiy, uiv2, vix, v2x} n E(G) = 0, then G[{u, v, x, y, u1, v1, v2}] contains a subgraph isomorphic to Gi3 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, assume that uiy, uiv2, vix, v2x G E(G). Since G has no induced cycle of length at least 5, uiz, wui G E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, there is wi such that such that uiwi, wiw G E(G). Since G is K1j3-free, wiy, wix G E(G). This implies that G[{wi,ui, w, y}] is an induced Ki 3, a contradiction.
If d(u) = 6 and d(v) = 6, let N(u)\{v, w, z, x} = {ui, u2} and N(v)\{u, w, z, y} = {vi,v2}. since G is K13-free, uix, u2x, uiu2, viy, v2y, viv2 G E(G). If either e({ui, u2}, {vi, v2}) > 2 or e({ui, u2}, {vi, v2}) = 1 and {uiy, uiv2, u2y, u2v2, u2vi}n E(G) = 0, then G[{u, v, x, y, ui, u2, vi,
v2}] contains a subgraph isomorphic to Gi4 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, e({ui, u2}, {vi, v2}) < 1. Moreover, if e({ui, u2}, {vi, v2} = 1 and uiy, uiv2, u2y, u2v2, u2vi G E(G). In this case, let uivi G E(G). Since G contains no induced cycle of length at least 5, wui, wu2, wvi, wv2, u2z G E(G). Consider the case that e({ui,u2}, {vi,v2}) =0. By Lemmas 2.4 and 3.2, e(x, {vi,v2}) < 1 and e(y, {ui, u2}) < 1. Since G contains no induced cycle of length at least 5, wu2, u2z G E(G). In each case, since k'(G) > 4 and G contains no induced cycle of length at least 5, there is wi such that such that u2wi, wiw G E(G) and wiy, wix G E(G). In this case, G contains a K1j3 induced by {wi, u2, w, y}, a contradiction.
Case 2. one edge of {xz, yz} is not in E(G).
We assume, without loss of generality, that xz G E(G) and yz G E(G). Since G is K1j3-free, wz G E(G). Consider that d(u) = d(v) = 4. Since ¿(G) > 4 and G is K1j3-free, d(y) = 4. Let {yi,y2} C N(y) \ {x, v}. Assume that one edge of yiz, y2z is in G, without loss of generality, assume that yiz G E (G). Since G is K13-free, yix,y2x,yiy2 G E(G). Let H = G[{u, v, w, x, y, z, yi,y2}]. Contracting the 2-cycle (yi, y2) in H[yyi ,yy2] and repeatedly contacting the 2-cycles generated in the process, eventually, we get a Ki which is Z3-connected. By Lemmas 2.1 and 2.2, H is Z3-connected, contrary to Lemma 3.2. Thus, yiz,y2z G E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, wyi G E(G) or wy2 G E(G). In each case, Contracting 2-cycle (u, w) and contracting all 2-cycle generated in the process in H[wu wz], we obtain a K- which is Z3-connected by Lemma 2.1 (1). By Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2.
If d(u) = 4 and d(v) = 5, let vi G N(v) \ {w, u,y, z}. Since G is K1j3-free, viy G E(G). Since k'(G) > 4, let yyi G E(G). Let H be the subgraph induced by {u, v, x, y, w, z, yi, vi}. Since G is K13-free, xyi G E(G). Since G contains no induced cycle of length at least 5, viw G E(G). We claim that vix G E(G) for otherwise, assume that vix G E(G). Since G is K1j3-free, yivi G E(G). Contracting 2-cycle (yi, vi) and contracting all 2-cycles generated in the process in H[xyi ,xvi], we get a K- which is Z3-connected by Lemma 2.1 (4). By Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2. If viz G E(G), by Lemma 3.2, viu, viw G E(G). In this case, the subgraph induced by {z, x, w, vi} is a K1j3, a contradiction. Thus, viz G E(G). If wyi G E(G), then H[wu wz] contains a 2-cycle (u, z). Contracting this 2-cycle and contracting all 2-cycles generated in the process, finally we obtain a K1. By Lemma 2.1 (1) (3) (5), and by Lemma 2.2, H is Z3-connected, contrary to Lemma 3.2. Thus, wy1 G E(G). Recall that wx G E(G). Since k'(G) > 4, there is a vertex w1 such that ww1, w1v1 G E(G). Since d(u) = 4
47
Ars Math. Contemp. 11 (2016) 35-47
and d(v) = 5, wiu, wiv € E(G). Since G has no induced cycle of length at least 5, wix € E(G). In this case, the subgraph induced by {w, w1, x, v1} is a K1j3, a contradiction.
If d(u) = 4 and d(v) = 6, let N(v) \ {w, u, x, z} = {v1, v2}. Since G is K1j3-free, yv1, yv2.v1v2 € E(G). Assume that v1z € E(G). Observe the subgraph G[{z, x, w, v1}]. Since G is K13-free, xv1 € E(G) or wv1 € E(G). In the former case, G contains a Z3-connected subgraph W4 induced by {z, u, x, v1,v} with the center at z, contrary to Lemma 3.2. In the latter case, G contains a Z3-connected subgraph W4 induced by {w, u, z, v1, v} with the center at v, contrary to Lemma 3.2. Thus, v1z € E(G). Similarly, v2z € E(G). If v1x, v2x € E(G), then G contains a Z3-connected subgraph K- induced by {y, x, v1, v, v2}, contrary to Lemma 3.2. Thus,|{v1x, v2x} n E(G)| < 1. Assume that v1x € E(G). Since G contains no induced cycle of length at least 5, wv1, wv2 € E(G). Since k'(G) > 4 and G contains no induced cycle of length at least 5, there exists a vertex w1 such that ww1,w1v1 € E(G) and w1x € E(G). In this case, G contains a K1j3 induced by {w1, w, x, v1}, a contradiction.
If d(u) = d(v) = 5, let N(u) \ {w, v, x, z} = {u1} and N(v) \ {w, u, y, z} = {v1}. Since G is K1j3-free, u1x, v1y € E(G). Since G is K1j3-free, zu1 € E(G). Since G has no induced cycle of length at least 5, wv1 € E(G). We claim that zv1 € E(G). To the contrary, assume that zv1 € E(G). Since G is K1j3-free, u1v1,xv1 € E(G). Let H = G[{u, v, w, x, y, z, u1, v1}]. Contracting the 2-cycle (u,x) in H[M1„ „1X] and repeatedly contacting the all 2-cycles generated in the process, eventually, we get a K1 which is Z3-connected. By Lemmas 2.1 and 2.2, H is Z3-connected, contrary to Lemma 3.2. Thus, v1z € E(G). In this case, since k'(G) > 4, there is a path Q from u1 to v1 avoiding any vertex in {z, w, u, v}. Since G has no induced cycle of length at least 5, |E(Q) | = 1, that is, v1u1 € E(G). If u1y € E(G) or v1x € E(G), then G[{u, v, x, y, u1, v1}] contains a subgraph isomorphic to G7 + e which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, u1y, v1x € E(G). Since G has no induced cycle of length at least 5, wu1 € E(G). As k'(G) > 4, there is a path P from w to v1. Since wv1 € E(G), there is w1 € V(G) such that w1w, w1 v1 € E(G). Since G has no induced cycle of length at least 5, w1x, w1y € E(G). Since G is K1j3-free, xv1 € E(G). This is a contradiction, as we have proved xv1 € E(G).
If d(u) = 5 and d(v) = 6, let N(u) \ {w, v, x, z} = {u1} and N(v) \ {w, u, y, z} = {v1, v2}. Since G is K1j3-free, u1x, v1y, v2y, v1v2, zu1 € E(G). Since G has no induced cycle of length at least 5, wv1, wv2 € E(G). We claim that none of {zv1, zv2} is in E(G). Suppose otherwise that assume that zv1 € E(G). Since G is K1j3-free, u1v1,xv1 € E(G). Let H = G[{u, v, w, x, y, z, u1, v1, v2}]. Then H is isomorphic to G14 + e, which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2. Thus, zv1,zv2 € E(G). As k'(G) > 4, there is a path P from u1 to v1 avoiding any vertex in {z, w, u, v, x, y}. Since G has no induced cycle of length at least 5, u1v1 € E(G). In this case, the subgraph induced by {u, v, x, y, z, u1, v1, v2} is also isomorphic to G14 + e, which is Z3-connected by Lemma 2.4, contrary to Lemma 3.2.
If d(u) = d(v) = 6, let N(u) \ {w, v, x, z} = {u1, u2} and N(v) \ {w, u, y, z} = {v1, v2}. Since G is K13-free, u1x, u2x, u1u2, v1y, v2y, v1v2, zu1, zu2 € E(G). This means that the subgraph induced by {z, u, u1, u2, x} is a K5, which is Z3-connected by Lemma 2.1, contrary to Lemma 3.2.
Acknowledgements The first author was supported by the Science Foundation of China (11171129) and by Doctoral Fund of Ministry of Education of China (20130144110001).
X. Li and J. Ma: Z3-connectivity of Ki:3-free graphs without induced cycle.
22
References
[1]	J. A. Bondy and U. S. R Murty, Graph Theory with Application, North-Holland, New York, 1976.
[2]	J. J. Chen, E. Eschen and H. J. Lai, Group connectivity of certain graphs, Ars Combin. 89 (2008), 141-158.
[3]	G. Fan and C. Zhou, Degree sum and Nowhere-zero 3-flows, Discrete Math. 308 (2008), 6233-6240.
[4]	G. Fan and C. Zhou, Ore condition and Nowhere-zero 3-flows, SIAM J. Discrete Math. 22 (2008), 288-294.
[5]	G. Fan, H. -J. Lai, R. Xu, C. Q. Zhang and C. Zhou, Nowhere-zero 3-flows in triangularly connected graphs, J. Combin. Theory, SerB 98 (2008), 1325-1336.
[6]	T. Fukunaga, All 4-edge-connected HHD-Free graphs are Z3 -connected, Graphs and Combin. 27 (2011), 647-659.
[7]	F. Jaeger, N. Linial, C. Payan and M. Tarsi, Group connectivity of graphs-a nonhomogeneous analogue of Nowhere-zero flow properties, J. Combin. Theory, Ser B 56 (1992), 165-182.
[8]	H. -J. Lai, Nowhere-zero 3-flows in locally connected graphs, J. Graph Theory. 4 (2003), 211-219.
[9]	H. -J. Lai, Group connectivity of 3-edge-connected chordal graphs, Graphs and Combin. 16 (2000), 165-176.
[10]	X. Li, H. -J. Lai and Y. Shao, Degree condition and Z3-connectivity, Discrete Math. 312
(2012),	1658-1669.
[11]	L. Li, X. Li and C. Shu, Group connectivity of bridged graphs, Graphs and Combin. 29
(2013),	1059-1066.
[12]	L. M. Lovasz, C. Thomassen, Y. Wu and C. -Q. Zhang, Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory, Ser. B 103 (2013), 587-598.
[13]	R. Luo, R. Xu, J. Yin and G. Yu, Ore-condition and Z3-connectivity, European J. Combin. 29 (2008), 1587-1595.
[14]	J. Ma and X. Li, Nowhere-zero 3-flows of claw-fre graphs, Discrete Math. 336 (2014), 57-68.
[15]	C. Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory, Ser. B 102 (2012), 521-529.
[16]	W. T. Tutte, A contribution on the theory of chromatic polynomial, Canad. J. Math. 6 (1954), 80-91.
[17]	J. Yin and Y. Zhang, Posa-condition and nowhere-zero 3-flows, Discrete Math. 311 (2011), 897-907.
[18]	X. Zhang, M. Zhan, R. Xu, Y. Shao, X. Li and H. -J. Lai, Degree sum condition for Z3-connectivity, Discrete Math. 310 (2010), 3390-3397.