Improved bounds for the coefficient of flow polynomials

2025/02/18 by Wu, Tingzeng, Ma, Shuang, Lai, Hong-Jian
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2502.12773

Abstract

Let G be a connected bridgeless (n,m)-graph which may have loops and multiedges, and let F(G,t) denote the flow polynomial of G. Dong and Koh \citeDong1 established an upper bound for the absolute value of coefficient c_i of tⁱ in the expansion of F(G,t), where 0\leqslant i \leqslant m-n+1. In this paper, we refine the aforementioned bound. Specifically, we demonstrate that when n \leqslant m \leqslant n+3, |c_i|\leqslant d_i, where d_i is the coefficient of tⁱ in the expansion ∏_j=1^m-n+1(t+j); and when m\geqslant n+4, |c_i|\leqslant d_i, with d_i being the coefficient of tⁱ in the expansion (t+1)(t+2)(t+3)²(t+4)^m-n-3. Furthermore, we prove that if G is a connected bridgeless cubic graph having only real flow roots, then b_i\leqslant |c_i|, where b_i is the coefficient of tⁱ in the expansion (t+1)(t+2)^(n)/(2). Notably, if G is simple connected bridgeless cubic graph with only real flow roots, then b_i is the coefficient of tⁱ in the expansion (t+1)(t+2)^(n)/(2)-2(t+3)².

Related

• On Zero-free Intervals of Flow Polynomials
• Several extreme coefficients of the Tutte polynomial of graphs
• On graphs whose flow polynomials have real roots only
• Graphs whose flow polynomials have only integral roots
• Flow polynomials of a signed graph