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

Abstract

Let $r\ge 2$ be a real number. A complex nowhere-zero $r$-flow on a graph $G$ is an orientation of $G$ together with an assignment $\phi :E(G)\to \mathbb{C}$ such that, for all $e\in E(G)$, the modulus of the complex number $\phi (e)$ lies in the interval $[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$, denoted by ${\varphi }_{\mathbb{C}}(G)$, is the minimum of the real numbers $r$ such that $G$ admits a complex nowhere-zero $r$-flow. The exact computation of ${\varphi }_{\mathbb{C}}$ seems to be a hard task even for very small and symmetric graphs. In particular, the exact value of ${\varphi }_{\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 non trivial lower bound for ${\varphi }_{\mathbb{C}}(G)$ in terms of the odd-girth of a cubic graph $G$ (i.e. the length of a shortest odd cycle) and we show that such lower bounds are tight. Our main result, Theorem 2, relies on the exact computation of the complex flow number of the wheel graph $W_n$ (see Theorem 1). In particular, we show that for every odd $n$, the value of ${\varphi }_{\mathbb{C}}(W_n)$ arises from one of three suitable configurations of points in the complex plane according to the congruence of $n$ modulo $6$.

24 pages, 10 figures