Bounds for the coefficients of flow polynomials

Abstract

Let G be any connected bridgeless (n, m)-graph which may have loops and multiedges. It is known that the flow polynomial F (G, t) of G is a polynomial of degree m - n + 1; F (G, t) = t - 1 if m = n; and F (G, t) ∈ {(t - 1)2, (t - 1) (t - 2)} if m = n + 1. This paper shows that if m ≥ n + 2, then the absolute value of the coefficient of ti in the expansion of F (G, t) is bounded above by the coefficient of ti in the expansion of (t + 1) (t + 2) (t + 3) (t + 4)m - n - 2 for each i with 0 ≤ i ≤ m - n + 1. © 2006 Elsevier Inc. All rights reserved.