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

DOI10.1002/JGT.23075arXiv2303.10281WikidataQ128261068 ScholiaQ128261068MaRDI QIDQ6430005FDOQ6430005

Authors: Davide Mattiolo, G. Mazzuoccolo, Jozef Rajník, Gloria Tabarelli 

Publication date: 17 March 2023

Abstract: Let $rgeq2$ be a real number. A complex nowhere-zero $r$-flow on a graph $G$ is an orientation of $G$ together with an assignment $varphicolonE(G)omathbbC$ such that, for all $einE(G)$, the modulus of the complex number $varphi(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 $ph{i}_{mathbbC}(G)$, is the minimum of the real numbers $r$ such that $G$ admits a complex nowhere-zero $r$-flow. The exact computation of $ph{i}_{mathbbC}$ seems to be a hard task even for very small and symmetric graphs. In particular, the exact value of $ph{i}_{mathbbC}$ 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 $ph{i}_{mathbbC}(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 $ph{i}_{mathbbC}(W_n)$ arises from one of three suitable configurations of points in the complex plane according to the congruence of $n$ modulo $6$.

Mathematics Subject Classification ID

Flows in graphs (05C21)

This page was built for publication: A lower bound for the complex flow number of a graph: a geometric approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430005)