Mathematics – Combinatorics
Scientific paper
2003-09-19
J. Combinatorial Th. Ser. B 96, no. 6 (2006), 901-918
Mathematics
Combinatorics
17 pages, to appear in J. Combinatorial Th. Ser. B
Scientific paper
A nowhere-zero $k$-flow on a graph $\Gamma$ is a mapping from the edges of $\Gamma$ to the set $\{\pm1, \pm2, ..., \pm(k-1)\} \subset \bbZ$ such that, in any fixed orientation of $\Gamma$, at each node the sum of the labels over the edges pointing towards the node equals the sum over the edges pointing away from the node. We show that the existence of an \emph{integral flow polynomial} that counts nowhere-zero $k$-flows on a graph, due to Kochol, is a consequence of a general theory of inside-out polytopes. The same holds for flows on signed graphs. We develop these theories, as well as the related counting theory of nowhere-zero flows on a signed graph with values in an abelian group of odd order. Our results are of two kinds: polynomiality or quasipolynomiality of the flow counting functions, and reciprocity laws that interpret the evaluations of the flow polynomials at negative integers in terms of the combinatorics of the graph.
Beck Matthias
Zaslavsky Thomas
No associations
LandOfFree
The Number of Nowhere-Zero Flows on Graphs and Signed Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Number of Nowhere-Zero Flows on Graphs and Signed Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Number of Nowhere-Zero Flows on Graphs and Signed Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-276172