Nowhere-zero 3 3 -flows in Cayley graphs on solvable groups of twice square-free order

Milad Ahanjideh, István Kovács · 2026

Read Nowhere-zero 3 3 -flows in Cayley graphs on solvable groups of twice square-free order by Milad Ahanjideh, István Kovács (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24175.txt.

Introduction

Ahanjideh and Kovács verify Tutte's 3-flow conjecture for a class of Cayley graphs. The conjecture claims certain graphs admit a flow that is nowhere zero with values in a small group. They settle it for Cayley graphs on solvable groups of order twice a square-free number. Their proof rests on a new necessary and sufficient condition. That condition describes when a simple 5-valent graph has a nowhere-zero 3-flow, in terms of a special pseudoforest decomposition. The condition turns a flow question into a structural one.

Catalog record

CREATORMilad Ahanjideh, István Kovács
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76323
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24175

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nowhere-zero 3 3 -flows in Cayley graphs on solvable groups of twice square-free order Milad Ahanjideh, István Kovács Abstract We verify Tutte’s 3 3 -flow conjecture in the class of Cayley graphs on solvable groups of order 2 ​ n 2n , where n n is square-free. The proof relies on a new necessary and sufficient condition for a simple 5 5 -valent graph to admit a nowhere-zero 3 3 -flow in terms of a pseudoforest decomposition. Keywords: nowhere-zero 3 3 -flow, pseudoforest, Cayley graph, solvable group. Math. Subj. Class.: 05C21, 05C25. 1 Introduction Let \Gamma be a finite simple graph. An orientation of \Gamma is a digraph D whose vertex set is equal to the vertex set \mathrm{V}(\Gamma) and its arcs are obtained from \Gamma by endowing each edge of \Gamma with one of the two possible directions. For an edge e of \Gamma , let D(e) denote the associated arc of D , and for a vertex v\in\mathrm{V}(\Gamma) , denote by D^{+}(v) the set of edges \Gamma that the associated arcs in D have tail v and by D^{-}(v) the set of those edges that the associated arcs in D have head v . Let A be an abelian group with the operation written additively and with identity element 0 . An A -flow in \Gamma is a pair (D,\varphi) , where D is an orientation of \Gamma and \varphi is an A -valued function on the edge set \mathrm{E}(\Gamma) , such that for every vertex v\in\mathrm{V}(\Gamma) , \sum_{e\in D^{+}(v)}\varphi(e)=\sum_{e\in D^{-}(v)}\varphi(e). In addition, if \varphi(e)\neq 0 for every e\in\mathrm{E}(\Gamma) , then (D,\varphi) is called a nowhere-zero A -flow . A \mathbb{Z} -flow (D,\varphi) is called a k -flow if |f(e)|<k for every e\in\mathrm{E}(\Gamma) , here \mathbb{Z} stands for the additive group of integers and k is a fixed positive integer. The concept of nowhere-zero flows was introduced by Tutte [ 12 , 13 ] in connection with his work on the Four Color Conjecture. He showed that the Four Color Conjecture holds if and only if all bridgeless planar graphs admit a nowhere-zero 4 -flow. Tutte proposed three conjectures on k -flows in graphs which are still open. In this paper we are interested in his 3 -flow conjecture, which reads as follows. Conjecture 1.1 . (Tutte) Every 4 -edge-connected graph admits a nowhere-zero 3 -flow. This conjecture has been studied extensively. Jaeger [ 5 ] showed that every 4 -edge-connected graph admits a nowhere-zero 4 -flow and he also conjectured the existence of a positive integer k , for which every k -edge-connected graph admits a nowhere-zero 3 -flow. Thomassen [ 14 ] showed that Jaeger’s conjecture holds for k=8 , which was improved by Lovász et al. [ 8 ] , who proved that every 6 -edge-connected graph admits a nowhere-zero 3 -flow. In this paper, we focus on Conjecture 1.1 in the class of Cayley graphs. This class has attracted considerable attention [ 1 , 4 , 7 , 10 , 11 , 15 , 17 , 16 ] . Let G be a finite group with identity element 1 and X\subseteq G be a subset such that 1\notin X and X=X^{-1}:=\{x^{-1}\mid x\in X\} . Then the Cayley graph \mathrm{Cay}(G,X) is defined to have vertex set G and for any g,h\in G , there is an edge joining g and h if and only if g^{-1}h\in X . The set X is referred to as the connection set . It is well-known that every connected k -valent Cayley graph is k -edge-connected [ 9 ] , and therefore, in the class of Cayley graphs, Conjecture 1.1 is equivalent to saying that every connected Cayley graph on a group G of valency at least 4 admits a nowhere-zero 3 -flow. This statement is known to be true if G is (i) an abelian [ 11 ] or nilpotent [ 10 ] or dihedral group [ 4 ] ; or (ii) a generalized dihedral or generalized quaternion [ 7 ] or generalized dicyclic group [ 1 ] ; or (iii) a supersolvable group with a non-cyclic Sylow 2 -subgroup or a group with a derived subgroup of square-free order [ 16 ] ; or (iv) a group of order p^{2}q [ 15 ] or 8p [ 17 ] , where p and q are distinct primes. Note that all groups listed in (i)–(iv) are solvable. In this paper, we consider another infinite family of solvable groups. Our main result is the following theorem. Theorem 1.2 . Let G be a solvable group of order 2n , where n is square-free. Then every connected Cayley graph of valency at least 4 on G admits a nowhere-zero 3 -flow. Remark 1.3 . It is worth mentioning that the result on the groups in (i)–(iii) was also shown to be true for the broader family of Cayley multigraphs (for the definition, see Section 2 ). However, this is not true for the group G considered in Theorem 1.2 . An example of a 5 -valent Cayley multigraph on the alternating group A_{4} , which does not admit a nowhere-zero 3 -flow, is provided in Example 4.2 . The paper is organized as follows. In Section 2 , we collect the concepts and results needed throughout the paper. Previous works follow an approach based on detecting certain closed ladders as subgraphs. This approach was proposed by Nánásiová and Škoviera [ 10 ] and was later developed into the concept of a generalized closed ladder by Zhang and Zhou [ 16 ] . Using this method, we derive a new sufficient condition for a graph of valency 5 to admit a nowhere-zero 3 -flow (see Lemma 2.9 ). In Section 3 , we introduce a new approach based on pseudoforests. Roughly speaking, we give a necessary and sufficient condition for a 5 -valent graph \Gamma to admit a nowhere-zero 3 -flow in terms of a partition of the vertex set \mathrm{V}(\Gamma) into two subsets such that the subgraphs of \Gamma induced by these subsets are pseudoforests and there exists a matching of \Gamma between these subsets satisfying certain condition (see Lemma 3.2 ). After all preparations are completed, the proof of Theorem 1.2 is presented in Section 4 . 2 Preliminaries All groups and graphs in this paper are finite and unless otherwise stated, all graphs are simple. For a graph \Gamma , the vertex set of \Gamma is denoted by \mathrm{V}(\Gamma) and the edge set of \Gamma by \mathrm{E}(\Gamma) . If \{u,v\} is an edge of \Gamma , then we will write u\sim v . For subgraphs \Gamma_{1},\Gamma_{2}\subseteq\Gamma with \mathrm{V}(\Gamma)=\mathrm{V}(\Gamma_{1})\cup\mathrm{V}(\Gamma_{2}) and \mathrm{E}(\Gamma)=\mathrm{E}(\Gamma_{1})\cup\mathrm{E}(\Gamma_{2}) , we write \Gamma=\Gamma_{1}\cup\Gamma_{2} . For a subset U\subseteq\mathrm{V}(\Gamma) , the subgraph of \Gamma induced by U is denoted by \Gamma[U] . If W\subseteq\mathrm{V}(\Gamma) is another subset disjoint with U , then \Gamma[U,W] denotes the bipartite graph having bipartition parts U and W and the edges \{u,w\}\in\mathrm{E}(\Gamma) with u\in U and w\in W . For a subset E\subseteq\mathrm{E}(\Gamma) , the subgraph of \Gamma obtained from \Gamma by deleting all edges in E from \mathrm{E}(\Gamma) is denoted by \Gamma-E . If each vertex of \Gamma has even valency, then \Gamma is called even ; and a subgraph \Gamma^{\prime}\subseteq\Gamma is called

Read the complete text