2018/08/01 by Dong, Fengming
#05C21 #05C31 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.00175
Let G be a bridgeless graph. In 2011 Kung and Royle showed that all roots of the flow polynomial F(G,λ) of G are integers if and only if G is the dual of a chordal and plane graph. In this article, we study whether a bridgeless graph G for which F(G,λ) has real roots only must be the dual of some chordal and plane graph. We conclude that the answer of this problem for G is positive if and only if F(G,λ) does not have any real root in the interval (1,2). We also prove that for any non-separable and 3-edge connected G, if G-e is also non-separable for each edge e in G and every 3-edge-cut of G consists of edges incident with some vertex of G, then all roots of P(G,λ) are real if and only if either G∈ \L,Z3,K4\ or F(G,λ) contains at least 9 real roots in the interval (1,2), where L is the graph with one vertex and one loop and Z3 is the graph with two vertices and three parallel edges joining these two vertices.