کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656971 | 1343704 | 2013 | 34 صفحه PDF | دانلود رایگان |

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 real roots 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→∞.
Journal: Journal of Combinatorial Theory, Series B - Volume 103, Issue 4, July 2013, Pages 532-565