2014/03/08 by Fengming Dong, Dong, Fengming
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1403.1916
26 pages, 7 figures
arxiv created 2014/03/08 · arxiv updated 2014/03/11
This article studies real roots of the flow polynomial F(G,λ) of a bridgeless graph G. For any integer k≥ 0, let ξk be the supremum in (1,2] such that F(G,λ) has no real roots in (1,ξk) for all graphs G with |W(G)|≤ k, where W(G) is the set of vertices in G of degrees larger than 3. We prove that ξk can be determined by considering a finite set of graphs and show that ξk=2 for k≤ 2, ξ3=1.430⋯, ξ4=1.361⋯ and ξ5=1.317⋯. We also prove that for any bridgeless graph G=(V,E), if all roots of F(G,λ) are real but some of these roots are not in the set \1,2,3\, then |E|≥ |V|+17 and F(G,λ) has at least 9 real roots in (1,2).