Polynomials counting nowhere-zero chains in graphs (Q2073314)

Summary: We introduce polynomials counting nowhere-zero chains in graphs -- nonhomogeneous analogues of nowhere-zero flows. For a graph \(G\), an Abelian group \(A\), and \(b:V(G)\to A\), let \(\alpha_{G,b}\) be a mapping from \(\Lambda(G)\) (a family of vertex sets of connected subgraphs of \(G\) satisfying an additional condition) to \(\{0,1\}\) such that for each \(X\in\Lambda(G)\), \(\alpha_{G,b}(X)=0\) if and only if \(\sum_{v\in X}b(v)=0\). We prove that there exists a polynomial function \(F(G,\alpha;k)\) \((\alpha=\alpha_{G,b})\) of \(k\) such that for any Abelian group \(A^\prime\) of order \(k\) and each \(b^\prime:V(G)\to A^\prime\) satisfying \(\alpha_{G,b^\prime}=\alpha\), \(F(G,\alpha;k)\) equals the number of nowhere-zero \(A^\prime\)-chains \(\varphi\) in \(G\) having boundaries equal to \(b^\prime\). In particular \(F(G,\alpha;k)\) is the flow polynomial of \(G\) if \(\alpha(X)=0\) for each \(X\in\Lambda(G)\). Finally we characterize \(\alpha\) for which \(F(G,\alpha;k)\) is nonzero and show that in this case \(F(G,\alpha;k)\) has the same degree as the flow polynomial of \(G\).