The Number of Nowhere-Zero Tensions on Graphs and Signed Graphs

Abstract

A nowhere-zero $k$-tension on a graph $G$ is a mapping from the edges of $G$ to the set $\{\pm 1,\pm 2,\dots ,\pm (k-1)\}\subset \mathbb{Z}$ such that, in any fixed orientation of $G$, for each circuit $C$ the sum of the labels over the edges of $C$ oriented in one direction equals the sum of values of the edges of $C$ oriented oppositely. We show that the existence of an integral tension polynomial that counts nowhere-zero $k$-tension on a graph, due to Kochol, is a consequence of a general theory of inside-out polytopes. The same holds for tensions on signed graphs. We develop these theories, as well as the related counting theory of nowhere-zero tensions on signed graphs with values in an abelian group of odd order. Our results are of two kinds: polynomiality or quasipolynomiality of the tension counting functions, and reciprocity laws that interpret the evaluations of the tension polynomials at negative integers in terms of the combinatorics of the graph.