Tutte initiated the study of nowhere-zero flows and proved the following fundamental theorem: For every graph $G$ there is a polynomial $f$ so that for every abelian group $\Gamma$ of order $n$, the number of nowhere-zero $\Gamma$-flows in $G$ is $f(n)$. For signed graphs (which have bidirected orientations), the situation is more subtle. For a finite group $\Gamma$, let $\epsilon_2(\Gamma)$ be the largest integer $d$ so that $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}_2^d$. We prove that for every signed graph $G$ and $d \ge 0$ there is a polynomial $f_d$ so that $f_d(n)$ is the number of nowhere-zero $\Gamma$-flows in $G$ for every abelian group $\Gamma$ with $\epsilon_2(\Gamma) = d$ and $|\Gamma| = 2^d n$. Beck and Zaslavsky [JCTB 2006] had previously established the special case of this result when $d=0$ (i.e., when $\Gamma$ has odd order).
@article{10_37236_7958,
author = {Matt DeVos and Edita Rollov\'a and Robert \v{S}\'amal},
title = {A note on counting flows in signed graphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {2},
doi = {10.37236/7958},
zbl = {1441.05096},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7958/}
}
TY - JOUR
AU - Matt DeVos
AU - Edita Rollová
AU - Robert Šámal
TI - A note on counting flows in signed graphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7958/
DO - 10.37236/7958
ID - 10_37236_7958
ER -
%0 Journal Article
%A Matt DeVos
%A Edita Rollová
%A Robert Šámal
%T A note on counting flows in signed graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7958/
%R 10.37236/7958
%F 10_37236_7958
Matt DeVos; Edita Rollová; Robert Šámal. A note on counting flows in signed graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/7958
