2023/03/17 by Davide Mattiolo, Mattiolo, Davide, Giuseppe Mazzuoccolo +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.10281
openalex publication_date 2023/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let r ≥ 2 be a real number. A complex nowhere-zero r-flow on a graph G is an orientation of G together with an assignment φ\colon E(G)→ ℂ such that, for all e ∈ E(G), the modulus of the complex number φ(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 ϕℂ(G), is the minimum of the real numbers r such that G admits a complex nowhere-zero r-flow. The exact computation of ϕℂ seems to be a hard task even for very small and symmetric graphs. In particular, the exact value of ϕℂ 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 ϕℂ(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 Wn (see Theorem 1). In particular, we show that for every odd n, the value of ϕℂ(Wn) arises from one of three suitable configurations of points in the complex plane according to the congruence of n modulo 6.