Is the five-flow conjecture almost false? Articles uri icon

publication date

  • August 2013

start page

  • 532

end page

  • 565

issue

  • 4

volume

  • 103

international standard serial number (ISSN)

  • 0095-8956

electronic international standard serial number (EISSN)

  • 1096-0902

abstract

  • The number of nowhere zero Z(Q) flows on a graph G can be shown to be a polynomial in Q, defining the flow polynomial Phi(G)(Q). According to Tutte's five-flow conjecture, Phi(G)(5) > 0 for any bridgeless G. A conjecture by Welsh that Phi(G)(Q) has no real roots for Q is an element of (4, infinity) was recently disproved by Haggard, Pearce and Royle. These authors conjectured the absence of roots for Q is an element of [5, infinity). We study the real roots of Phi(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 approximate to 5.0000197675 and Q approximate to 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 -> infinity (in the latter case from above and below); and that Q(c)(7) approximate to 5.2352605291 is an accumulation point of real zeros of the flow polynomials for G(7n, 7) as n -> infinity. (C) 2013 Elsevier Inc. All rights reserved.

keywords

  • nowhere zero flows; flow polynomial; flow roots; tutteʼs five-flow conjecture; petersen graph; transfer matrix