- July 2013
Digital Object Identifier (DOI)
International Standard Serial Number (ISSN)
Electronic International Standard Serial Number (EISSN)
- 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.
- nowhere zero flows; flow polynomial; flow roots; tutte's five-flow conjecture; petersen graph; transfer matrix