A lower bound for the complex flow number of a graph: A geometric approach

• Published in: Journal of graph theory 2024-06, Vol.106 (2), p.239-256
• Main Authors: Mattiolo, Davide, Mazzuoccolo, Giuseppe, Rajník, Jozef, Tabarelli, Gloria
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; complex flow; Complex numbers; Computation; Congruences; cubic graph; Graphs; Lower bounds; nowhere‐zero flow; Real numbers
• ISSN: 0364-9024; 1097-0118
• DOI: 10.1002/jgt.23075

Let r≥2 $r\ge 2$ be a real number. A complex nowhere‐zero r $r$‐flow on a graph G $G$ is an orientation of G $G$ together with an assignment φ:E(G)→C $\varphi :E(G)\to {\mathbb{C}}$ such that, for all e∈E(G) $e\in E(G)$, the Euclidean norm of the complex number φ(e) $\varphi (e)$ lies in the interval [1,r−1] $[1,r-1]$ and, for every vertex, the incoming flow is equal to the outgoing flow. The complex flow number of a bridgeless graph G $G$, denoted by ϕC(G) ${\phi }_{{\mathbb{C}}}(G)$, is the minimum of the real numbers r $r$ such that G $G$ admits a complex nowhere‐zero r $r$‐flow. The exact computation of ϕC ${\phi }_{{\mathbb{C}}}$ seems to be a hard task even for very small and symmetric graphs. In particular, the exact value of ϕC ${\phi }_{{\mathbb{C}}}$ is known only for families of graphs where a lower bound can be trivially proved. Here, we use geometric and combinatorial arguments to give a nontrivial lower bound for ϕC(G) ${\phi }_{{\mathbb{C}}}(G)$ in terms of the odd‐girth of a cubic graph G $G$ (i.e., the length of a shortest odd cycle) and we show that this lower bound is tight. This result relies on the exact computation of the complex flow number of the wheel graph Wn ${W}_{n}$. In particular, we show that for every odd n $n$, the value of ϕC(Wn) ${\phi }_{{\mathbb{C}}}({W}_{n})$ arises from one of three suitable configurations of points in the complex plane according to the congruence of n $n$ modulo 6.