Publication: Is the five-flow conjecture almost false?
Loading...
Identifiers
Publication date
2013-07
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Impact
Export
Abstract
The number of nowhere zero ZQ flows on a graph G can be shown to be a polynomial in Q, defining the flow polynomial ΦG(Q). According to Tutte’s five-flow conjecture,ΦG(5)>0 for any bridgeless G. A conjecture by Welsh that ΦG(Q) has no realroots for Q∈(4,∞) was recently disproved by Haggard, Pearce and Royle. These authors conjectured the absence of roots for Q∈[5,∞). We study the real roots of ΦG(Q) for a family of non-planar cubic graphs known as generalised Petersen graphs G(m,k). We show that the modified conjecture on real flow roots is also false, by exhibiting infinitely many real flow roots Q>5 within the class G(nk,k). In particular, we compute explicitly the flow polynomial of G(119,7), showing that it has real roots at Q ≈ 5.0000197675 and Q ≈ 5.1653424423. We moreover prove that the graph families G(6n,6) and G(7n,7) possess real flow roots that accumulate at Q = 5 as n→∞ (in the latter case from above and below); and that Qc(7) ≈ 5.2352605291 is an accumulation point of real zeros of the flow polynomials for G(7n,7) as n→∞
Description
Keywords
Nowhere zero flows, Flow polynomial, Flow roots, Tutte's five-flow conjecture, Petersen graph, Transfer matrix
Bibliographic citation
Jacobsen, J. L. & Salas, J. (2013). Is the five-flow conjecture almost false? Journal of Combinatorial Theory, Series B, 103(4), pp. 532–565.