1. A lower bound for the complex flow number of a graph: A geometric approach.
- Author
-
Mattiolo, Davide, Mazzuoccolo, Giuseppe, Rajník, Jozef, and Tabarelli, Gloria
- Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF