/^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 10 (2016) 85-90
Nowhere-zero 3-flows in graphs admitting solvable arc-transitive groups of automorphisms*
Xiangwen Li t
Department of Mathematics, Huazhong Normal University, Wuhan 430079, China
Sanming Zhou *
School of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia
Received 18 February 2014, accepted 20 May 2014, published online 8 July 2015
Abstract
Tutte's 3-flow conjecture asserts that every 4-edge-connected graph has a nowhere-zero 3-flow. In this note we prove that every regular graph of valency at least four admitting a solvable arc-transitive group of automorphisms admits a nowhere-zero 3-flow.
Keywords: Integer flow, nowhere-zero 3-flow, vertex-transitive graph, arc-transitive graph, solvable group.
Math. Subj. Class.: 05C21, 05C25
1 Introduction
All graphs in this paper are finite and undirected, and all groups considered are finite. Let r = (V(r), E(r)) be a graph endowed with an orientation. For an integer k > 2, a k-flow [3] in r is an integer-valued function f : E(r) ^ {0, ±1, ±2,..., ±(k - 1)} such that, for every v e V(r),
E f (e)= E f (^
e£E+(v)	e£E-(v)
where E+ (v) is the set of edges of r with tail v and E- (v) the set of edges of r with head v. A k-flow f in r is called a nowhere-zero k-flow if f (e) = 0 for every e e E(r). Obviously,
* The authors are grateful to an anonymous referee for his/her comments which led to improved presentation. ^Li was supported by the National Natural Science Foundation of China (11171129).
tZhou was supported by a Future Fellowship of the Australian Research Council. Part of the work was done when he visited Huazhong Normal University in 2011.
E-mail addresses: xwli68@mail.ccnu.edu.cn (Xiangwen Li), smzhou@ms.unimelb.edu.au (Sanming Zhou)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
86
ArsMath. Contemp. 10(2016)85-90
if r admits anowhere-zero k-flow, then r admits a nowhere-zero (k+1)-flow. It is also easy to see that whether a graph admits a nowhere-zero k-flow is independent of its orientation. The notion of nowhere-zero flows was introduced by Tutte in [20, 21] who proved that a planar graph admits a nowhere-zero 4-flow if and only if the Four Color Conjecture holds. The reader is referred to Jaeger [9] and Zhang [25] for surveys on nowhere-zero flows and to [3, Chapter 21] for an introduction to this area.
In [20, 21] Tutte proposed three celebrated conjectures on integer flows which are still open in general. One of them is the following well-known 3-flow conjecture (see e.g. [3, Conjecture 21.16]).
Conjecture 1.1. (Tutte's 3-flow conjecture) Every 4-edge-connected graph admits a nowhere-zero 3-flow.
This conjecture has been extensively studied in over four decades; see e.g. [6, 7,10,11, 12, 19, 23, 24]. Solving a long-standing conjecture by Jaeger [8] (namely the weak 3-flow conjecture), recently Thomassen [19] proved that every 8-edge-connected graph admits a nowhere-zero 3-flow. This breakthrough was further improved by Lovasz, Thomassen, Wu and Zhang [12] who proved the following result.
Theorem 1.2. ([12, Theorem 1.7]) Every 6-edge-connected graph admits a nowhere-zero 3-flow.
It is well known [22] that every vertex-transitive graph of valency d > 1 is d-edge-connected. Thus, when restricted to the class of vertex-transitive graphs, Conjecture 1.1 asserts that every vertex-transitive graph of valency at least four admits a nowhere-zero 3-flow. Due to Theorem 1.2 this is now boiled down to vertex-transitive graphs of valency 5, since every regular graph with even valency admits a nowhere-zero 2-flow. In an attempt to Tutte's 3-flow conjecture for Cayley graphs, Potocnik, Skoviera and Skerkovski [16] proved the following result. (It is well known [2] that every Cayley graph is vertex-transitive, but the converse is not true.)
Theorem 1.3. ([16, Theorem 1.1]) Every Cayley graph of valency at least four on an abelian group admits a nowhere-zero 3-flow.
This was generalized by Nanasiova and Skoviera [13] to Cayley graphs on nilpotent groups.
Theorem 1.4. ([13, Theorem 4.3]) Every Cayley graph of valency at least four on a nilpotent group admits a nowhere-zero 3-flow.
It would be nice if one can prove Tutte's 3-flow conjecture for all vertex-transitive graphs. As a step towards this, we prove the following result in the present paper.
Theorem 1.5. Every regular graph of valency at least four admitting a solvable arc-transitive group of automorphisms admits a nowhere-zero 3-flow.
Note that any G-arc-transitive graph is necessarily G-vertex-transitive and G-edge-transitive. On the other hand, any G-vertex-transitive and G-edge-transitive graph with odd valency is G-arc-transitive. (This result is due to Tutte, and its combinatorial proof given in [4, Proposition 1.2] can be easily extended from G = Aut(r) to a subgroup G of Aut(r).) Therefore, Theorem 1.5 is equivalent to the following: For any solvable group
X. Li and S. Zhou: Nowhere-zero 3-flows in graphs admitting solvable
87
G, every G-vertex-transitive and G-edge-transitive graph with valency at least four admits a nowhere-zero 3-flow.
In Section 3 we will prove a weaker version (Claim 1) of Theorem 1.5, which together with Theorem 1.2 implies Theorem 1.5. Note that none of Theorems 1.5 and 1.4 is implied by the other, because not every Cayley graph is arc-transitive, and on the other hand an arc-transitive graph is not necessarily a Cayley graph (see e.g. [2, 17]).
At this point we would like to mention a few related results. Alspach and Zhang (1992) conjectured that every Cayley graph with valency at least two admits a nowhere-zero 4-flow. Since every 4-edge-connected graph admits a nowhere-zero 4-flow [8], this conjecture is reduced to the cubic case. Alspach, Liu and Zhang [1, Theorem 2.2] confirmed this conjecture for cubic Cayley graphs on solvable groups. This was then improved by Nedela and Skoviera [14] who proved that any counterexample to the conjecture of Alspach and Zhang must be a regular cover over a Cayley graph on an almost simple group. (A group G is almost simple if it satisfies T < G < Aut(T) for some simple group T.) In [15], Potocnik proved that every connected cubic graph that admits a solvable vertex-transitive group of automorphisms is 3-edge-colourable or isomorphic to the Petersen graph. This is another generalization of the result of Alspach, Liu and Zhang above, because Petersen graph is not a Cayley graph, and for cubic graphs 3-edge-colourability is equivalent to the existence of a nowhere-zero 4-flow.
It would be pleasing if one can replace arc-transitivity by vertex-transitivity in Theorem 1.5. As an intermediate step towards this, one may try to prove that every Cayley graph of valency at least four on a solvable group admits a nowhere-zero 3-flow, thus generalizing Theorem 1.4 and the above-mentioned result of Alspach, Liu and Zhang simultaneously.
2 Preparations
We follow [3] and [5, 18] respectively for graph- and group-theoretic terminology and notation. The derived subgroup of a group G is defined as G' := [G, G], the subgroup of G generated by all commutators x-1 y-1xy, x, y G G. Define G(0) := G, G(1) := G' and G(i) := (G(i-1))' for i > 1. A group G is solvable if there exists an integer n > 0 such that G(n) = 1; in this case the least integer n with G(n) = 1 is called the derived length of G. Solvable groups with derived length 1 are precisely nontrivial abelian groups. In the proof of Theorem 1.5 we will use the fact that any solvable group contains an abelian normal subgroup with respect to which the quotient group has a smaller derived length.
All definitions in the next three paragraphs are standard and can be found in [2, Part Three] or [17].
Let G be a group acting on a set Q. That is, for each (a, g) G Q x G, there corresponds an element a9 G Q such that a1 = a and (a9)h = agh for any a G Q and g, h G G, where 1 is the identity element of G. We say that G is transitive on Q if for any a, P G Q there exists at least one element g G G such that a9 = P, and regular if for any a, P G Q there exists exactly one element g G G such that a9 = p. The group G is intransitive on Q if it is not transitive on Q. A partition P of Q is G-invariant if P9 := {a9 : g G G} G P for any P gP and g G G, and nontrivial if 1 < |P | < |Q| for every P gP .
Suppose that r is a graph admitting G as a group of automophisms. That is, G acts on V(r) (not necessarily faithfully) such that, for any a, P G V(r) and g G G, a and P are adjacent in r if and only if a9 and P9 are adjacent in r. (If K is the kernel of the action of G on V(r), namely, the subgroup of all elements of G that fix every vertex of r, then
88
Ars Math. Contemp. 10 (2016) 99-112
G/K is isomorphic to a subgroup of the automorphism group Aut(T) of r.) We say that r is G-vertex-transitive if G is transitive on V(T), and G-edge-transitive if G is transitive on the set of edges of r. If r is G-vertex-transitive such that G is also transitive on the set of arcs of r, then r is called G-arc-transitive, where an arc is an ordered pair of adjacent vertices.
Let r be a graph and P a partition of V(T). The quotient graph of r with respect to P, denoted by Tp, is the graph with vertex set P in which P, Q e P are adjacent if and only if there exists at least one edge of r joining a vertex of P and a vertex of Q. For blocks P, Q e P adjacent in Tp, denote by r[P, Q] the bipartite subgraph of r with vertex set P U Q whose edges are those of r between P and Q. In the case when all blocks of P are independent sets of r and r[P, Q] is a t-regular bipartite graph for each pair of adjacent P, Q e P, where t > 1 is an integer independent of (P, Q), we say that r is a multicover of rp. A multicover with t = 1 is thus a topological cover in the usual sense. In the proof of Theorem 1.5, we will use the following lemma in the case when k = 3.
Lemma 2.1. Let k > 2 be an integer. If a graph admits a nowhere-zero k-flow, then its multicovers all admit a nowhere-zero k-flow.
Proof. Using the notation above, let r be a multicover of E := Tp. Suppose that E admits a nowhere-zero k-flow f (with respect to some orientation). For each oriented edge (P, Q) of E, orient the edges of the t-regular bipartite graph r[P, Q] in such a way that they all have tails in P and heads in Q, and then assign f (P, Q) to each of them. Denote this nowhere-zero function on the oriented edges of r by g, and denote the oriented edge of r with tail a and head ft by (a, ft). It can be verified that, for any P e P and
a e P, £(a,iS)£E+(a) ft) = £(P,Q)£E+ (P) t • f (P Q) and £(,8,a)£E-(a) g(ft a) =
P)£E_(P) t • f (Q, P). Since f is a nowhere-zero k-flow in E, for every P e P, we
have
£ f (P, Q) = £ f (Q,P).
(P,Q)£E+(P)	(Q,P)£E-(P)
Therefore, for every a e V(r), we have
£ g(a, ft)= £ g(ft, a) (a„S)£E+(a)	(¡3,a)£E-(a)
and so g is a nowhere-zero k-flow in r.	□
If r is a G-vertex-transitive graph, then for any normal subgroup N of G, the set PN := {aN : a e V(r)} of N-orbits on V(r) is a G-invariant partition of V(r), called a G-normal partition of V(r) [17], where aN := {ag : g e N}. Denote the corresponding quotient graph by rN := TpN. The quotient group G/N induces an action on PN defined by (aN)Ng = (ag)N. The following observations can be easily proved (see e.g. [17]).
Lemma 2.2. ([17]) Let r be a connected G-vertex-transitive graph, and N a normal subgroup of G that is intransitive on V (r). Then the following hold:
(a)	rN is G/N-vertex-transitive under the induced action of G/N on PN;
(b)	for P, Q e PN adjacent in rN, r[P, Q] is a regular subgraph of r;
(c)	if in addition r is G-arc-transitive, then rN is G/N-arc-transitive and r is a multicover of rN.
X. Li and S. Zhou: Nowhere-zero 3-flows in graphs admitting solvable
89
3 Proof of Theorem 1.5
By Theorem 1.2, in order to prove Theorem 1.5 it suffices to prove that, for any finite solvable group G, every G-arc-transitive graph of valency five admits a nowhere-zero 3-flow. We will prove the following seemingly stronger but equivalent result:
Claim 1. For any solvable group G, every G-arc-transitive graph with valency at least four and not divisible by three admits a nowhere-zero 3-flow.
We will prove this by induction on the derived length of the solvable group G, using Theorem 1.3 as the base case. We will use the following fact [2, Lemma 16.3]: a graph is isomorphic to a Cayley graph if and only if its automorphism group contains a subgroup that is regular on the vertex set. Denote by val(T) the valency of a regular graph r.
Without loss of generality we may assume that the solvable group G is faithful on the vertex set of the graph under consideration for otherwise we can replace G by its quotient group (which is also solvable) by the kernel of G on the vertex set. Under this assumption G is isomorphic to a subgroup of the automorphism group of the graph. We may also assume that the graph under consideration is connected (for otherwise we consider its components). We make induction on the derived length n(G) of G.
Suppose that n(G) = 1 and r is a G-arc-transitive graph with val(r) > 4. Then G is abelian and so is regular on V(r). (A transitive abelian group must be regular.) Since G is isomorphic to a subgroup of Aut(r), it follows that r is isomorphic to a Cayley graph on G. Thus, by Theorem 1.3, r admits a nowhere-zero 3-flow.
Assume that, for some integer n > 1, the result (in Claim 1) holds for any solvable group of derived length at most n. Let G be a solvable group with derived length n(G) = n +1. Let r be a connected G-arc-transitive graph such that val(r) > 4 and val(r) is not divisible by 3. If val(r) is even, then r admits a nowhere-zero 2-flow and hence a nowhere-zero 3-flow. So we assume that val(r) > 5 is odd. Since 3 does not divide val(r) by our assumption, every prime factor of val(r) is no less than 5. Since G is solvable, it contains an abelian normal subgroup N such that the quotient group G/N has derived length at most n(G) - 1 = n. Note that G/N is solvable (as any quotient group of a solvable group is solvable) and N =1 (for otherwise G/N = G would have derived length n(G)). If N is transitive on V(r), then it is regular on V(r) as N is abelian. In this case r is isomorphic to a Cayley graph on N and so admits a nowhere-zero 3-flow by Theorem 1.3.
In what follows we assume that N is intransitive on V(r). By Lemma 2.2, rN is a connected G/N-arc-transitive graph, and r is a multicover of rN. Thus val(rN) is a divisor of val(r) and so is not divisible by 3. If val(rN) = 1, then r is a regular bipartite graph of valency at least two and so admits a nowhere-zero 3-flow [3]. Assume that val(rN) > 1. Then val(rN) > 5 and every prime factor of val(rN) is no less than 5. Thus, since G/N is solvable of derived length at most n, by the induction hypothesis, rN admits a nowhere-zero 3-flow. Since r is a multicover of rN, by Lemma 2.1, r admits a nowhere-zero 3-flow. This completes the proof of Claim 1 and hence the proof of Theorem 1.5.
References
[1]	B. Alspach, Y.-P. Liu and C.-Q. Zhang, Nowhere-zero 4-flows and Cayley graphs on solvable groups, SIAMJ. Discrete Math. 9 (1996), 151-154.
[2]	N. L. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge University Press, Cambridge, 1993.
90	Ars Math. Contemp. 10 (2016) 99-112
[3]	J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
[4]	Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J. Combin. Theory Ser.B 42 (1987), 196-211.
[5]	J. D. Dixon and B. Mortimer, Permutation Groups, Springer, New York, 1996.
[6]	G. Fan and C. Zhou, Degree sum and Nowhere-zero 3-flows, Discrete Math. 308 (2008), 62336240.
[7]	G. Fan and C. Zhou, Ore condition and Nowhere-zero 3-flows, SIAM J. Discrete Math. 22 (2008), 288-294.
[8]	F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979), 205-216.
[9]	F. Jaeger, Nowhere-zero flow problems, in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory, Vol. 3, Academic Press, San Diego, 1988, 71-95.
[10]	H. -J. Lai, Nowhere-zero 3-flows in locally connected graphs, J. Graph Theory 4 (2003), 211219.
[11]	X. Li, Y. Shao, H.-J. Lai, Degree condition and Z3-connectivity, Discrete Math. 312 (2012), 1658-1669.
[12]	L. M. Lovasz, C. Thomassen, Y. Wu, C. -Q. Zhang, Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory Ser. B 103 (2013), 587-598.
[13]	M. Nanasiova and M. Skoviera, Nowhere-zero flows in Cayley graphs and Sylow 2-subgroups, J. Alg. Combin. 30 (2009), 103-110.
[14]	R. NedelaandM. Skoviera, Cayley snarks and almost simple groups, Combinatorica 21 (2001), 583-590.
[15]	P. Potocnik, Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms, J. Combin. Theory Ser. B 91 (2004), 289-300.
[16]	P. Potocnik, M. Skoviera and R. Skrekovski, Nowhere-zero 3-flows in abelian Cayley graphs, Discrete Math 297 (2005), 119-127.
[17]	C. E. Praeger, Finite transitive permutation groups and finite vertex transitive graphs, in: G. Hahn and G. Sabidussi (eds.), Graph Symmetry, Kluwer Academic Publishing, Dordrecht, 1997, 277-318.
[18]	J. J. Rotman, An Introduction to the Theory of Groups, 4th ed., Springer, New York, 1995.
[19]	C. Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory Ser. B 102 (2012), 521-529.
[20]	W. T. Tutte, A contribution on the theory of chromatic polynomial, Canad. J. Math. 6 (1954), 80-91.
[21]	W. T. Tutte, On the algebraic theory of graph colorings J. Combin. Theory 1 (1966), 15-50.
[22]	A. E. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970), 23-29.
[23]	J. Yan, Nowhere-zero 3-flows and Z3-connectivity of a family of graphs, Discrete Math. 311 (2011), 1988-1994.
[24]	F. Yang and X. Li, Nowhere-zero 3-flows in dihedral Cayley graphs, Information Processing Letters 111 (2011), 416-419.
[25]	C.-Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker Inc., New York, 1997.