/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 203-213
https://doi.org/10.26493/1855-3974.1406.cc1
(Also available at http://amc-journal.eu)
The validity of Tutte's 3-flow conjecture for some
Cayley graphs*
Milad Ahanjideh, Ali Iranmanesh
Faculty of Mathematical Sciences, Tarbiat Modares University, Tehran, Iran
Received 19 May 2017, accepted 12 June 2018, published online 24 November 2018
Abstract
Tutte's 3-flow conjecture claims that every bridgeless graph with no 3-edge-cut admits a nowhere-zero 3-flow. In this paper we verify the validity of Tutte's 3-flow conjecture on Cayley graphs of certain classes of finite groups. In particular, we show that every Cayley graph of valency at least 4 on a generalized dicyclic group has a nowhere-zero 3-flow. We also show that if G is a solvable group with a cyclic Sylow 2-subgroup and the connection sequence S with |S | > 4 contains a central generator element, then the corresponding Cayley graph Cay(G, S) admits a nowhere-zero 3-flow.
Keywords: Nowhere-zero flow, Cayley graph, Tutte's 3-flow conjecture, connection sequence, solvable group, nilpotent group.
Math. Subj. Class.: 05C25, 05C21, 20D10
1 Introduction
Let D be an orientation of a graph r and let k be a positive integer. A k-flow on a graph r is a pair (D, f) where f is an integer valued function
f: E(r) ^ Z
such that |f (e)| < k for every e G E(r), and for every v G V(r),
E f (e)= E f (e).
e£E(v) +	eeE(v)-
*The authors would like to thank Professor Martin Skoviera and Professor Saieed Akbari for their useful comments which improved the paper. Also we thank the anonymous referees for reading the paper carefully and making the useful suggestions.
E-mail addresses: ahanjidm@gmail.com (Milad Ahanjideh), iranmanesh@modares.ac.ir (Ali Iranmanesh)
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
204
ArsMath. Contemp. 16(2019)203-213
where E(v)+ and E(v) are the all edges with tails at v and heads at v, respectively. A nowhere-zero k-flow (abbreviated a k-NZF) is a pair (D, f) such that for every e G E(r),
f (e) = 0.
The following conjecture is due to Tutte and is known as Tutte's 3-flow conjecture:
Conjecture 1.1 (Tutte's 3-flow conjecture [8, 9]). Every bridgeless graph with no 3-edge-cut has a 3-NZF.
Although Tutte's 3-flow conjecture has been studied by many authors, it is still widely open.
Let G be a finite group with identity 1 and S = (s1; s2,..., sn) be a sequence of elements of G \ {1} such that the mapping sj ^ s-1 permutes the entries of S. We call S a connection sequence (note that all entries of S are distinct unless stated otherwise). A Cayley graph, denoted by Cay(G, S), is a graph whose vertex set is G with adjacency defined by
g ~ h if and only if g-1h G S,
for every g, h G G. We see at once that if S generates G, then Cay(G, S) is connected.
Alspach et al. [1] conjectured that every Cayley graph of valency at least 3 has a nowhere-zero 4-flow. They also showed their conjecture to be true for solvable groups. Their result was significantly strengthened and extended by Nedela and Skoviera to a much wider class of groups [5].
By combining the fact that a k-valent Cayley graph is k-edge-connected graph with the fact that every 4-edge-connected graph has a 4-NZF [2], we deduce that every Cayley graph of valency at least 4 has a 4-NZF. Thus the question about the existence of a nowhere-zero 4-flow is interesting only for cubic Cayley graphs. Since 4-regular graphs admit a nowhere-zero 2-flow, the important question about flows on Cayley graphs of valency greater than 3 is whether every Cayley graph of valency at least 5 has a nowhere-zero 3-flow. In other words, it is interesting to verify whether Tutte's 3-flow conjecture holds on such Cayley graphs.
In [6], it has been proved that every abelian Cayley graph of valency k, where k > 4, admits a 3-NZF. Nanasiova and Skoviera [4] improved the above result to Cayley graphs on a group G whose Sylow 2-subgroup is the direct factor of G, and as a consequence, they showed that every Cayley graph of valency at least 4 on a nilpotent group has a 3-NZF. Recently, Yang and Li [11] showed the same fact for a Cayley graph on a dihedral group, and L. Li and X. Li [3] verified Tutte's 3-flow conjecture for Cayley graphs on generalized dihedral groups and generalized quaternion groups.
In this paper, we investigate Tutte's 3-flow conjecture for Cayley graphs on a solvable group with a suitable normal subgroup (Theorems 3.1 and 3.2 and Remark 3.5) and as a consequence of these theorems, we show that every Cayley graph of valency at least 4 on a generalized dicyclic group satisfies Tutte's 3-flow conjecture. By using Theorem 3.6 we can obtain the results of [3] and [11] by a different method.
In [4], the authors showed that a Cayley graph of valency at least 4 with the connection sequence containing a central involution admits a 3-NZF. In Theorem 3.6, we extend this result to the case when Sylow 2-subgroups of G are cyclic and the connection sequence of G contains a central generator element. As a consequence of this theorem, we show that if a Cayley graph of valency at least 4 on a solvable group G, with a cyclic Sylow 2-subgroup, admits a 3-NZF, then every Cayley graph of valency at least 4 on the direct product of G and a nilpotent group admits a 3-NZF.
M. Ahanjideh and A. Iranmanesh: The validity ofTutte's 3-flow conjecture for some ... 205
2 Notation and preliminaries
The terminology and notation used in this paper are standard both in group theory and graph theory, see for instance [7, 10].
An element g of G is called an involution if g has order 2. Let Z(G) be the center of a group G. We say that an element x of G is central if x G Z(G). The group generated by a sequence S is denoted by (S) and the element x G G is named a generator element of G in S if (S \ {x}) = (S). For integers m, n > 2, a cycle of length n and a path of length m - 1 are denoted by Cn and Pm, respectively. For an integer m > 3 and for n G Zm, the Cayley graph Cay(Zm, {-1, 1, -n, n}) will be denoted by C(m, n). Let N be a subgroup of G and x belongs to a left transversal set of N in G. The image of Cay(N, S) under left translation by x is denoted by x Cay(N, S). The Cartesian product Hi □ H2 of graphs Hi and H2 is a graph such that V(Hi) x V(H2) is its vertex set and any two vertices (u, u') and (v, v') are adjacent in Hi □ H2 if and only if either u = v and u'v' G E(H2) or u' = v' and uv G E (Hi). Set L = P„ □ K2, where V (P„) = {1,2, ...,n} and V (K2) = {1,2}. The Mobius ladder MLn is a graph obtained by adding the edges (12)(n1) and (11)(n2) to L. Also, by adding the edges (11)(n1) and (12)(n2) to L, we obtain a graph is called the circular ladder CLn. In fact CLn = Cn □ K2. Any graph isomorphic to either CLn or MLn for some n will be referred to as a closed ladder. It is easy to check that the circular ladder is bipartite if and only if n is even while the Mobius ladder is bipartite if and only if n is odd.
Lemma 2.1 ([4, Theorems 3.3 and 4.3]). Let Cay(G, S) be a Cayley graph of valency k, where k > 4. If S contains a central involution, then Cay(G, S) has a 3-NZF In particular, if G is nilpotent, then Cay(G, S) has a 3-NZF
Lemma 2.2 ([4, Proposition 4.1]). Let G be a group, H be a normal subgroup of G and let S be a connection sequence with no intersection with H. If Cay(G/H, S/H) has a 3-NZF, then so does Cay(G, S).
Note that in Lemma 2.2, according to the paragraph before Proposition 4.1 in [4], for distinct elements s,t G S, we regard sH and tH as distinct elements of S/H. So,
Cay(G/H, S/H) may have parallel edges even when Cay(G, S) is simple and |S/H| = |S|.
Lemma 2.3 ([6, Theorem 1.1]). Every abelian Cayley graph of valency k, where k > 4, admits a 3-NZF.
Lemma 2.4 ([6, Proposition 2.5]). Let m, n > 3 be integers. Then the graph Cn □ Cm □ K2 admits a 3-NZF.
Lemma 2.5 ([6, Proposition 2.6]). Let m, n > 3 be two integers such that m > n > 1 and m > 3. Then the graph C(m, n) □ K2 admits a 3-NZF.
Lemma 2.6 ([6, Corollary 2.2]). A regular bipartite graph of valency at least 2 admits a 3-NZF.
Lemma 2.7 ([10, page 308]). A cubic graph has a 3-NZF if and only if it is bipartite.
Lemma 2.8. Let G be a group and N be a subgroup of G of index 2. Then Cay(G, S \ (S n N)) is bipartite.
206
Ars Math. Contemp. 16 (2019) 141-155
Proof. Since the index of N in G is 2, there exists d e G \ N such that G = N U dN. So, we can consider the vertices of Cay(G, S) as two partitions N and dN. Since for every m, n e N, m and n are adjacent, and dm and dn are adjacent if and only if m-1n e S n N, we obtain that Cay(G, S \ S n N) is a bipartite graph with partite sets N and dN. □
Lemma 2.9 ([10, page 308]). A graph has a 2-NZF if and only if it is an even graph.
Remark 2.10. According to the above lemma, for discussion about a nowhere-zero 3-flow in a Cayley graph with a connection sequence S, it is enough to investigate the case when |S| is odd.
Remark 2.11. Let G be a group and N be a subgroup of G. Let T = {x1;..., xt}, where t e N, be a left transversal set of N in G. If S is a connection sequence of N such that
Cay(N, S) is connected, then
{x, Cay(N, S) : 1 < i < t}
is the set of connected components of Cay(G, S). For every x, where i e {1,..., t},
Cay(N, S) and x, Cay(N, S) are isomorphic, because for every m, n e N,
x,m ~ x,n (in x, Cay(N, S n N)) if and only if
(xjm)-1(xjn) e S n N if and only if m-1n e S n N
if and only if m ~ n (in Cay(N, S n N)).
Thus if Cay(N, S) has a 3-NZF, then Cay(G, S) has a 3-NZF. Hence for finding a 3-NZF in Cay(G, S), we reduce to find a 3-NZF in Cay(N, S).
3 Main results
In this section we show the validity of Tutte's 3-flow conjecture for a solvable group with a suitable normal subgroup. As examples, we show the same result for Cayley graphs on generalized dicyclic groups, generalized dihedral groups and quaternion groups. We also prove that every Cayley graph Cay(G, S) on a solvable group G with a cyclic Sylow 2-subgroup such that the connection sequence S contains a central generator element, admits a 3-NZF.
Theorem 3.1. Let G be a solvable group, N be a subgroup of G of index 2 and let S be a connection sequence of G such that |S| > 5 is odd and S n Z(N) = 0. If
(1)	Cay(N, S n N) admits a 3-NZF and
(2)	for every d e S \ N, d-1(S n N)d = S n N, then Cay(G, S) has a 3-NZF.
Proof. Without loss of generality, we can assume that there exists an element d e S \ N, because otherwise S c N and by Condition (1), we could conclude that Cay(G, S) has a 3-NZF. Thus, there is d e S \ N. Note that |S| is odd. We continue the proof in the following two cases:
Case 1. If |S n N| is odd, then since |S \ (S n N)| = |S| \ |S n N| is even, Lemma 2.9 shows that Cay(G, S \ (S n N)) admits a 3-NZF. Also by Condition (1), Cay(N, S n N) admits a 3-NZF, and so does Cay(G, S) = Cay(G, S \ (S n N)) U Cay(G, S n N).
M. Ahanjideh and A. Iranmanesh: The validity ofTutte's 3-flow conjecture for some ... 207
Case 2. If |S n N| is even, then the proof will be divided into two subcases:
Subcase 1. Assume that |S\(S nN )| > 2. By Lemma 2.8, Cay(G, S\(S nN)) is bipartite. So Lemma 2.6 shows that Cay(G, S \ (S n N)) admits a 3-NZF. Since Cay(G, S n N) admits a 3-NZF, we deduce that Cay(G, S) has a 3-NZF.
Subcase 2. Assume that |S \ (S n N)| = 1. Thus {S \ (S n N)} = {d}, so O(d) = 2 and it is not hard to check that G is the semidirect product of N and (d). We want to show that Cay(N, S n N) □ Cay((d), {d}) = Cay(G, S). For this purpose, we define ^: Cay(N, S n N) □ Cay((d), {d}) ^ Cay(G, S) such that ^(m, x) = mx for every m G N and x G (d). Since G is the semidirect product of N and (d), it is obvious that ^ is a bijective function. Now we will show that ^ is homomorphism. For every m, n G N and x,y G (d), we have:
(m,x) - (n,y) (in Cay(N, S n N) □ Cay((d), {d}))
if and only if m = n, x — y or n — m, x = y.
We should check the following cases:
(1)	If m = n, x = 1 and y = d, then (^(m, x))-1 ^>(n, y) = m-1nd = d G S. Thus ^>(m, x) — ^>(n, y) in Cay(G, S).
(2)	If m = n, x = d and y =1, then (^(m, x))-1^(n, y) = d-1m-1n = d G S. Thus ^>(m, x) — ^>(n, y) in Cay(G, S).
(3)	If m — n and x = y =1, then m-1n G S n N. Thus (^(m, x))-1^(n, y) = (mx)-1(ny) = m-1n G N n S .So ^(m, x) — ^(n, y) in Cay(G, S).
(4)	If m — n and x = y = d, then m-1n G S n N. Thus (^(m, x))-1^(n, y) = d-1(m-1n)d G d-1 (S n N)d = N n S C S. So ^(m, x) — ^(n,y) in Cay(G,S).
Now, let t1 — t2 in Cay(G, S). Since G is the semidirect product of N and (d), there exist m, n G N and x, y G (d) such that t1 = mx and t2 = ny. We continue the proof in the following cases:
(i)	If x =1 and y = d, then m-1nd = t-1t2 G S\(SnN) = {d}. Therefore, m-1n = 1 and so m = n. From this, we have ^-1(t1) = (m, x) — (n, y) = ^-1(t2).
(ii)	If x = d and y = 1, the above reason shows that ^-1(t1) = (m, x) — (n, y) =
^-1(t2).
(iii)	If x = y =1, then m-1n = t-1t2 G S n N. Therefore m — n in Cay(N, S n N) and hence ^-1(t1) = (m, x) — (n, y) = ^-1(t2).
(iv)	If x = y = d, then d-1m-1nd = t-1t2 G d(S n N)d-1 = S n N. Therefore
m-1n G d(S n N)d-1 = S n N and hence, ^-1(t1) = (m,x) — (n, y) = ^-1(t2).
These show that Cay(N, SnN) □ Cay((d), {d}) = Cay(G, S). Now, suppose that the theorem is false, and let G be the smallest group satisfying the hypothesis and Cay(G, S) does not admit a 3-NZF. Note that |S| > 5. We examine the following possibilities:
Subcase 2.1. If there is y G S n Z(N) of order n > 2 such that d-1yd G {y,y-1}, then since Z(N) is normal in G, the assumption guarantees the existence of an element
z G S n Z(N) such that d-1yd = z. Since O(d) = 2, we see that d-1zd = y.
208
Ars Math. Contemp. 16(2019)203-213
Thus (y, y-1, z, z-1) < (y, y-1,z, z-1, d). If G = (y, y-1,z, z-1,d), then by our assumption on G, Cay((y, y-1, z, z-1 ,d), {y, y-1,z, z-1,d}) admits a 3-NZF. Thus since IS \ {y, y-1,z, z-1, d}| is even, we get that Cay(G, S) admits a 3-NZF. This is a contradiction. Therefore, we can assume that G = (y,y-1,z,z-1,d), N = (y,y-1,z,z-1), S = {y,y-1,z,z-1,d} and S n N = {y,y-1, z, z-1}. Let K be a minimal normal subgroup of G such that K < Z(N). If K n S = 0, then N/K < G/K with [G/K : N/K] = 2 and Z(N/K) n S/K = 0. Note that IS/K| = 5 and |(S n N)/K| = 4. So Cay(N/K, (S n N)/K) admits a 3-NZF. Also IG/K| < |G|. Thus our assumption on G leads us to see that Cay(G/K, S/K) admits a 3-NZF, and so does Cay(G, S) by Lemma 2.2. This is a contradiction. Thus K n S = 0. Without loss of generality, we can suppose that y G K, so d-1yd = z G K. Therefore, K = N. This forces N to be cyclic or elementary abelian. Thus either N = (y) or N = (S n N) = (y) x (z) and hence, either z = yl and
Cay(N, N n S) = Cay((y), {y, y-1,y\ y-i}) = C(n, i) or
Cay(N, N n S) = Cay((y), {y, y-1}) □ Cay((z), {z, z-1}) = C„ □ Cn.
Note that Cay(G, S) = Cay(N, S n N) □ K2. Thus Cay(G, S) is isomorphic to either C(n, i) □ K2 or (Cn □ Cn) □ K2. So Lemmas 2.5 and 2.4 guarantee that Cay(G, S) admits a 3-NZF. This is a contradiction.
Subcase 2.2. If S n Z(N) contains an involution y such that d-1 yd = y, then there exists an element z G S n Z (N ) such that d-1yd = z. Therefore, (y, z) is an elementary abelian 2-group of order 4. So Cay((y, z, d), {y, z, d}) is the circular ladder CL4 (see Figure 1) which is bipartite and hence, it admits a 3-NZF. Also, Cay(G, S\{y, z, d}) admits a 3-NZF, and so does Cay(G, S). This is a contradiction.
Figure 1: The circular ladder CL4.
Subcase 2.3. Suppose that for every y G Z(N) n S, d-lyd G {y/y-1}. Applying the above argument shows that there exists an element y G Z(N) n S such that (y) is a minimal normal subgroup of G. If the order of y is 2, then y is a central involution and hence, Cay(G, S) admits a 3-NZF. This is a contradiction. Thus the order of y is an odd prime number. Now if N n S contains an element z such that O(z) > 3 and d-1zd G {z, z-1}, then applying the same argument as that of used in Subcase 2.1 leads us to get a contradiction. Now suppose that there exists an element z g (SnN)\{y,y-1} such that O(z) > 3 and d-1zd G {z, z-1}. So our assumption on G allows us to assume that S = {y, y-1,z, z-1 ,d-1zd, d-1z-1d, d}. Let K be anormal subgroup of G containing y such that K < N and it is maximal with the property K n (S \ {y, y-1}) = 0. If M/K is a minimal normal subgroup of G/K such that M/K < N/K, then our assumption on K shows that M n (S \ {y, y-1}) = 0. Without loss of generality, we can assume that z G M. Since M is normal in G, we deduce that d-1zd G M and hence, S — {d} C M. Thus M = N. Set S1 = {z,z-1,d,-1zd,dr1z-1d,d,}. Moreover M/K = N/K is
M. Ahanjideh and A. Iranmanesh: The validity ofTutte's 3-flow conjecture for some ... 209
abelian and normal in G/K of index 2 such that S1/K \ (S1/K n M/K) = {dK} and dK(S1/K n M/K)dK = (S1/K n M/K). By our assumption on G, Cay(G/K, S1/K) admits a 3-NZF. But S1 n K = 0, so Lemma 2.2 shows that Cay(G, S1) admits a 3-NZF. In addition, since |S \ S11 = 2, Cay(G, S \ S1) admits a 3-NZF and hence, Cay(G, S) admits a 3-NZF. This is a contradiction. Finally, let N n S contain an element z of order 2. Since |S n N| is even, our assumption on G allows us to assume that there exists an involution w G (S n N) \ {z} such that G = (y, y-1, z, w, d). Since z, w are distinct involutions, we have that either (z, w) is an elementary abelian 2-group of order 4 or a dihedral group. We can see at once that Cay((w, z, d), {w, z, d}) is a circular ladder CLk, for some even number k, which is bipartite. Therefore, Cay((w, z, d), {w, z, d}) admits a 3-NZF, and so does Cay(G, S). This is a contradiction.
This shows that Cay(G, S) admits a 3-NZF, as desired.	□
Theorem 3.2. Let G be a group, N be an abelian subgroup of G of index 2 and let S be a connection sequence of G such that |S| > 4. If there exists d G S \ (S n N) such that d-1(S n N)d = S n N, then Cay(G, S) admits a 3-NZF.
Proof. First, assume that |S n N| > 4. By Lemma 2.3, Cay(N, S n N) has a 3-NZF. Since |G/N| = 2, we can assume that G/N = (dN), and hence for every y G S \ (S n N), yN G (dN). Thus there exists t G N such that y = td and
for every s G S n N and y G S \ (S n N), y-1sy G S n N.	(3.1)
So the Conditions (1) and (2) of Theorem 3.1 are fulfilled and hence Cay(G, S) admits a 3-NZF. Now, we assume that |S n N| < 3. The proof falls naturally into several parts. If |S n N| =0, then by Lemma 2.8, Cay(G, S) is bipartite, and hence Lemma 2.6 shows that Cay(G, S) admits a 3-NZF. Moreover, if |S n N| = 2, then Lemma 2.9 forces Cay(N, S n N) to admit a 3-NZF. Also by (3.1), for every s G S n N, y-1sy = d-1sd G S n N. So Theorem 3.1 completes the proof. Therefore, |S n N| G {1, 3}. We consider these possibilities in the following cases:
Case 1. Assume that |S n N| = 1. So S n N = {x}. Clearly, O(x) = 2 and d-1xd = x-1 = x. Also, for every y G S \ (S n N), we have yN G (dN) and hence, y = md for some m G N. Therefore, we can see y-1xy = x. Thus x G Z((S)) is of order 2. Hence by Lemma 2.1, we have Cay((S), S) admits a 3-NZF, and so does Cay(G, S).
Case 2. Assume that |S n N| = 3. We continue the proof in two subcases:
Subcase 1. Let S n N = {x, y, y-1}, where O(x) = 2 and O(y) > 3. Since d-1xd G S n N and O(d-1xd) = 2, the same argument as that of used in Case 1 completes the proof.
Subcase 2. Let S n N = {x, y, z}, where O(x) = O(y) = O(z) = 2. First, assume that none of the elements in S n N generates by the other ones. Since x, y, z are of order 2 and N is abelian, we have
(N n S) = {xy z1 | 1 < i, j, k < 2} = (x) x (y) x (z) < N.
It is easy to check that Cay( (N n S), S n N) is bipartite (similar to Figure 1) and hence by Lemma 2.6, Cay(N, S n N) admits a 3-NZF. The rest of the proof runs as the case when
|S n N| > 4.
210
ArsMath. Contemp. 16(2019)203-213
Otherwise, without loss of generality, assume that S n N — {x, y,xy}. Set S1 — {d, d-1}. Note that |S| is odd. Thus |S \ ((S n N) U Si)| — 0 or 2k where k G N. Set S2 — S \ ((S n N) U S1) and H — ((S n N) U S1). In fact,
Cay(G, S2) U Cay(G, (S n N) U S1) — Cay(G, S)
and Cay(G, S2) admits a 3-NZF. So it is sufficient to find a 3-NZF in Cay(G, (SnN) US1).
We know that d-1xd G S n N. If d-1xd — x, then since N is abelian, we have x G Z(H) and its order is 2, so the proof is complete by Lemma 2.1. Now, assume that
d-1xd — y. Since N — dN G G/N and |G/N| — 2, we have O(dN) — 2, and hence d2 G N. It follows that x — d2xd-2 — dyd-1. Therefore,
Thus xy G Z(H) and O(xy) — 2. Lemma 2.1 shows that Cay(H, (S n N) U S1) admits a 3-NZF, and so does Cay(G, (S n N) U S1), as desired. The same reasoning can be applied
In the following we show that Theorem 3.2 guarantees the existence of a 3-NZF in a Cayley graph on a generalized dicyclic group.
Example 3.3. Let H be an abelian group, having a specific element y G H of order 2. A group G is called a generalized dicyclic group, Dic(H, y), if it is generated by H and an additional element x. Moreover, we have [G : H] — 2, x2 — y and x-1ax — a-1 for every a G H .It is easy to see that every Cayley graph of valency at least 4 on Dic(H, y) has a 3-NZF by applying Theorem 3.2.
Note that in [3, 11], as the main theorems, it is showed that the graphs mentioned in Example 3.4 admit nowhere-zero 3-flows.
Example 3.4.
(1)	Let H be an abelian group. The generalized dihedral group DH is a group of order 2|H| generated by H and an element p where p G H, p2 — 1 and p-1hp — h-1 for all h G H. We see at once that every Cayley graph of valency at least 4 on DH satisfies the conditions of Theorem 3.2, and hence it admits a 3-NZF. In particular,
G — (x, a | an — x2 — 1, x-1ax — a-1) is a special case of DH, where H — (a), p — x and it is called a dihedral group and denoted by D2n.
(2)	Let G — (z, a | an — z2,an — 1,z-1az — a-1) which is called a generalized quaternion group, denoted by Q4n. Note that G is a special case of a generalized dicyclic group where (a) and z play the roles of H and x, respectively. Thus every Cayley graph of valency at least 4 on Q4n admits a 3-NZF.
Remark 3.5. Let G be a group, N be a normal subgroup of G of an odd index at least 3 and S be a connection sequence of G such that |S| > 4. Assume that T — {x1;..., x2k+1} is a left transversal set of N in G and Cay(N, S n N)) has a 3-NZF. Note that by Remark 2.11,
d 1xyd — d 1xdd 1yd — yx — xy.
to the case d-1 xd — xy.
□
Cay(G, S) —	x, Cay(N, S n N) I U Cay(G, S \ (S n N)).
i=1
M. Ahanjideh and A. Iranmanesh: The validity ofTutte's 3-flow conjecture for some ... 211
By the assumption, for every i e {1,..., 2k + 1}, x® Cay(N, S n N) admits a 3-NZF. For finding a 3-NZF in Cay(G, S), it is enough to find a 3-NZF in Cay(G, S \ (S n N)). If |S \ (S n N)| is odd, then there exists y e S \ (S n N) such that O(y) =2 and hence yN e G/N and O(yN) = 2. So we have 2 | |G/N|. This is impossible. Thus |S \ (S n N) | is even and hence Cay(G, S \ (S n N)) admits a 3-NZF by Lemma 2.9. Therefore if Cay(N, S n N) has a 3-NZF, then so does Cay(G, S).
Theorem 3.6. Let G be a solvable group with a cyclic Sylow 2-subgroup and let S be a connection sequence of G with |S| > 4. If there exists an element x e Z (G) n S such that x is a generator element of G in S, then Cay(G, S) admits a 3-NZF.
Proof. Suppose that G is the smallest counterexample satisfies the above conditions, but Cay(G, S) does not admit a 3-NZF. Without loss of generality, we can assume that |S| = 5 and x e Z(G) n S. Thus O(x) > 3 by Lemma 2.1. If there exists u e Z(G) such that (u)nS = 0, then |S/(u)| = |S|, x(u) e Z(G/(u))nS/(u) and |G/(u)| < |G|. Ifx(u) isa generator element of G/(u) in S/(u), then by our assumption, Cay(G/(u), S/(u)) admits a 3-NZF. Lemma 2.2 forces Cay(G, S) to admit a 3-NZF, a contradiction. Thus x(u) is not a generator element. Therefore, there exist an element t e (S \ {x, x-1}) and i e N such that xu® = t and hence t e Z(G). If there exists t1 e (t) n S, then as stated above, we can see that O(t1) > 3. Thus Z(G) n S = {x, x-1,t1,t-1}. Therefore |G/Z(G)| e {1,2} and hence, G/Z(G) is cyclic. So G is an abelian group. This forces Cay(G, S) to admit a 3-NZF, a contradiction. Thus (t) n S = 0. Moreover, we can see at once that x(t) is a generator element of G/(t) in S/(t), |S/(t)| = |S| and |G/(t)| < |G|. Therefore, our assumption forces Cay(G/ (t), S/ (t)) to admit a 3-NZF, and so does Cay(G, S) by Lemma 2.2. This is a contradiction. So for every u e Z(G), we have (u) n S = 0. We continue the proof in two cases:
Case 1. Suppose that |Z(G)| is even. So there exists w e Z(G) of order 2. By our assumption, (w) n S = 0, and hence S contains a central involution. Lemma 2.1 shows that Cay((S), S) admits a 3-NZF, and so does Cay(G, S). This is a contradiction.
Case 2. Let |Z(G)| be odd. Since |S| = 5, S contains an involution y. We continue the proof in three subcases:
Subcase 1. Suppose that |S n Z(G)| is odd, so Z(G) contains an involution. This is a contradiction, because |Z(G)| is odd.
Subcase 2. Suppose that |Z(G)nS| = 2. So we have Z(G)nS = {x,x-1}, where O(x) is an odd prime number p. Therefore, (x) is a cyclic subgroup of order p. By the assumption, x e (S \ {x, x-1}) and hence, we deduce that G = (x) x M, where M = (S \ {x, x-1}) is a maximal subgroup of G. Let N be a minimal normal subgroup of G such that N < M. So N is an elementary abelian q-group, where q is a prime number. If N n S = 0, then x(N) e Z(G/N) n S/N is a generator element of G/N in S/N, |G/N| < |G| and |S/N| = 5. Thus by our assumption on G, Cay(G/N, S/N) admits a 3-NZF, and so does Cay(G, S). This contradicts our assumption. If N n S = 0, then the proof falls naturally into several parts:
(a) If y e N n S such that O(y) = 2, then 2 | |N|. Since N is elementary abelian, we get that N is an elementary abelian 2-group. Thus | N| = 2 by the assumption. Therefore y e N < Z(G), and hence |Z(G)| is even. This is a contradiction.
213
ArsMath. Contemp. 16(2019)203-213
(b) If N n S = {z,z-1}, where O(z) > 3, then S \{x,x-1} = {z,z-1,y}. Since N is an elementary abelian q-group where q is a prime number, we get O(z) = q = 2. So y G N .If yz = zy, then G is an abelian group and hence, Lemma 2.3 forces Cay(G, S) to admit a 3-NZF, a contradiction. If yz = zy and O(yz) = 2, then we have yzy = z-1. Thus L = (x, x-1, z, z-1) < G = (x, x-1, z, z-1, y). Therefore, [G : L] = 2 and L < G. We thus get that Cay(G, S) admits a 3-NZF by Theorem 3.1. This is a contradiction. Now, suppose that yz = zy and O(yz) > 3. Since O(z) = q, z G N and |M/N| = |(yN)| = 2, we have |M| = 2q4, where t G N. If O(yz) = qn, where n < t, then yz G N. So y G N, a contradiction. Suppose that O(yz) = 2qn where n < t. Since gcd(2, qn) = 1, there exist k, s G Z such that 2s + kqn = 1. So, O((yz)2s) = qn and O((yz)fcq") = 2. Thus we have (yz)2s G N. Since z G N and N is abelian, we can see that (yz)2sy = y(yz)2s. Therefore (yz)2s G Z(M) < Z(G). Thus ((yz)2s) is a normal subgroup of G and ((yz)2s) < N .So z G N = ((yz)2s) < Z (M) < Z (G) and hence yz = zy. This is a contradiction with the above statements.
Subcase 3. Suppose that |S n Z(G)| = 4. Since |S| = 5, we can see |S|\|S n Z(G)| = 1. It follows that [(S) : (S n Z(G))] = 2. So (S)/((S n Z(G))) is a cyclic group. On the other hand, (S n Z(G)) < Z((S)). Therefore (S) is abelian, and hence Lemma 2.3 yields that Cay((S), S) admits a 3-NZF, and so does Cay(G, S), a contradiction.	□
Corollary 3.7. Let G be a solvable group such that the Sylow 2-subgroups of G are cyclic and every Cayley graph of valency at least 4 on G admits a 3-NZF. If H is a nilpotent group, then every Cayley graph of valency at least 4 on G x H admits a 3-NZF.
Proof. Suppose that H is the smallest nilpotent group such that Cay(G x H, S) does not admit a 3-NZF. Note that by the assumption on G, we have H = 1. If there exists 1 = t G Z(H) such that (t) n S = 0, then since (t) < G x H, our assumption on H shows that Cay((G x H)/ (t), S/ (t)) admits a 3-NZF. So Lemma 2.2 forces Cay(G x H, S) to admit a 3-NZF. This is a contradiction. Thus for every t G Z(H), (t) n S = 0. If |H| is even, then S contains a central involution and hence, Lemma 2.1 shows that Cay(G x H, S) admits a 3-NZF, a contradiction. Thus |H| is odd. Let the order of t G Z(H) n S be odd. If |H n S| is odd, then 2 | |H|. This is a contradiction. If |H n S| = 2, then H n S = {x, x-1} and hence, Z(H) n S = {x, x-1} and O(x) is a prime number. Since G is solvable, we can assume that K is a normal subgroup of G x H such that K < G and K is maximal with the property that S n K = 0. If G = K, then (G x H)/G is nilpotent and |S/G| = |S|, and hence, Cay((G x H)/G, S/G) admits a 3-NZF, and so does Cay(G x H, S). This is a contradiction. Thus G = K and for a minimal normal subgroup M/K of (G x H)/K such that M/K < G/K, we have M n S = 0. So one of the following possibilities occurs:
(I) Suppose that M n S contains an involution z. Then 2 | |M/K|. Since M/K is elementary abelian and the Sylow 2-subgroups of G are cyclic, we have M/K = (zK) and hence (zK) < Z((G x H)/K). Therefore, Lemma 2.1 shows that Cay((G x H)/K, S/K) admits a 3-NZF, and so does Cay(G x H, S) by Lemma 2.2, a contradiction.
(II) If M n S does not contain any involution, then |M n S| is an even number. Since |S| is odd, we get that S \ (M n S) contains an involution z. But |H| is odd, so z G G.
Let S1 = (M n S) U {z,x,x-1}. We have (S1) = (M n S,z) x (x) and |S1| > 5 is an odd number. Thus Theorem 3.6 shows that Cay((S1), S1) admits a 3-NZF, so
M. Ahanjideh and A. Iranmanesh: The validity ofTutte's 3-flow conjecture for some ... 171
does Cay(G x H, Si). Since |S \ Si| is even, Cay(G x H, S) admits a 3-NZF, a contradiction.
If |H n S| > 4, then there exists an element x G S such that O(x) = 2. Since |H| is odd, we have x G H n S and the Sylow 2-subgroups of G x H are the Sylow 2-subgroups of G and hence, x G G. Therefore x G CGxH(H n S), the centralizer of H n S in G x H, and hence x G Z((H n S) x (x)). So Lemma 2.1 forces Cay((H n S) x (x), (H n S) U {x}) to admit a 3-NZF, so does Cay(G x H, (H n S) U {x}). But |S \ ((H n S) U {x}) | is even, So Cay(G x H, S) admits a 3-NZF, a contradiction.	□
Corollary 3.8. If L is a nilpotent group, then for every generalized dihedral group DH, the Cayley graph of valency at least 4 on DH x L admits a 3-NZF.
Proof. Let DH be the smallest generalized dihedral group such that the Cayley graph of valency at least 4 on DH x L does not admit a 3-NZF. If |H | is odd, then the Sylow 2-subgroups of Dh are cyclic, and hence Corollary 3.7 shows that Cay(DH x L, S) admits a 3-NZF, a contradiction. If |H | is even, then H contains a central involution t. If t G S, then Lemma 2.1 shows that the Cayley graph of valency at least 4 on DH x L admits a 3-NZF, a contradiction. If t G S, then by our assumption, Cay((DH x L)/(t), S/(t)) admits a 3-NZF. It follows that Cay(DH x L, S) admits a 3-NZF by Lemma 2.2. This is impossible. These contradictions show that every Cayley graph of valency at least 4 on DH x L admits a 3-NZF.	□
References
[1]	B. Alspach, Y. Liu and C. Zhang, Nowhere-zero 4-flows and Cayley graphs on solvable groups, SIAMJ. Discrete Math. 9 (1996), 151-154, doi:10.1137/s0895480193258017.
[2]	F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Ser. B 26 (1979), 205-216, doi:10.1016/0095-8956(79)90057-1.
[3]	L. Li and X. Li, Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group, Front. Math. China 10 (2015), 293-302, doi:0.1007/ s11464-014-0378-2.
[4]	M. Nanasiova and M. Skoviera, Nowhere-zero 3-flows in Cayley graphs and Sylow 2-subgroups, J. Algebraic Combin. 30 (2009), 103-111, doi:10.1007/s10801-008-0153-0.
[5]	R. Nedela and M. Skoviera, Cayley snarks and almost simple groups, Combinatorica 21 (2001), 583-590, doi:10.1007/s004930100014.
[6]	M. Potocnik, P. Skoviera and R. Skrekovski, Nowhere-zero 3-flows in abelian Cayley graphs, Discrete Math. 297 (2005), 119-127, doi:10.1016/j.disc.2005.04.013.
[7]	J. S. Rose, A Course on Group Theory, Cambridge University Press, Cambridge, 1978.
[8]	W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80-91, doi:10.4153/cjm-1954-010-9.
[9]	W. T. Tutte, On the algebraic theory of graph colorings, J. Comb. Theory 1 (1966), 15-50, doi:10.1016/s0021-9800(66)80004-2.
[10]	D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996.
[11]	F. Yang and X. Li, Nowhere-zero 3-flows in dihedral Cayley graphs, Inform. Process. Lett. 111 (2011), 416-419, doi:10.1016/j.ipl.2011.01.017.