Flow polynomials of a signed graph

Jianguo Qian

Published 2018-05-21Version 1

In contrast to ordinary graphs, the number of the nowhere-zero group-flows in a signed graph may vary with different groups, even if the groups have the same order. In fact, for a signed graph $G$ and non-negative integer $d$, it was shown that there exists a polynomial $F_d(G,x)$ such that the number of the nowhere-zero $\Gamma$-flows in $G$ equals $F_d(G,x)$ evaluated at $k$ for every Abelian group $\Gamma$ of order $k$ with $\epsilon(\Gamma)=d$, where $\epsilon(\Gamma)$ is the largest integer $d$ such that $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}^d_2$. We aim to give an expression of $F_d(G,x)$. We first define the fundamental directed circuits for a signed graph $G$ and show that all $\Gamma$-flows (not necessarily nowhere-zero) in $G$ can be generated by these circuits. Moreover, we show that all $\Gamma$-flows in $G$ can be evenly partitioned into $2^d$-classes specified by the elements of order 2 in $\Gamma$. This gives an explanation for why the number of the $\Gamma$-flows in a signed graph varies with different $\epsilon(\Gamma)$, and also gives an answer to a problem posed by Beck and Zaslavsky. Based on this result, we establish an explicit expression of $F_d(G,x)$ for any non-negative integer $d$. Further, using an extension of Whitney's broken circuit theory we give a combinatorial interpretation of the coefficients in $F_d(G,x)$ for $d=0$, in terms of the broken bonds. As an example, we give an analytic expression of $F_0(G,x)$ for a class of the signed graphs which contain no balanced circuit. Finally, we show that the broken bonds in a signed graph form a homogeneous simplicial complex.