×

The number of nowhere-zero tensions on graphs and signed graphs. (English) Zbl 1265.05527

Let us fix an orientation of a given graph \(G\). Let \(\Gamma \) be an Abelian group. A nowhere-zero \(\Gamma \)-tension on \(G\) is a mapping from the edges of \(G\) to \(\Gamma \setminus \{0\}\) such that 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. Notice that the number of nowhere-zero \(\Gamma \)-tensions is independent of the fixed orientation of \(G\). A \(k\)-tension is a \(\mathbb {Z}_k\)-tension. The authors show that the existence of an integral tension polynomial that counts nowhere-zero \(k\)-tensions on a graph, due to M. Kochol [J. Graph Theory 40, No. 3, 137–146 (2002; Zbl 1004.05025)], is a consequence of a general theory of inside-out polytopes. The authors also study the counting theory of nowhere-zero tensions on signed graph with values in an Abelian group of odd order. The 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.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
05C31 Graph polynomials

Citations:

Zbl 1004.05025