RT Journal Article
T1 Is the five-flow conjecture almost false?
A1 Jacobsen, Jesper Lykke
A1 Salas Martínez, Jesús
AB 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→∞
PB Elsevier
SN 0095-8956
YR 2013
FD 2013-07
LK https://hdl.handle.net/10016/33034
UL https://hdl.handle.net/10016/33034
LA eng
NO The research of J.S. was supported in part by Spanish MICINN/MINECO grants MTM2008-03020,FPA2009-08785, MTM2011-24097 and FIS2012-34379, and by U.S. National Science Foundation grant PHY-0424082. The research of J.L.J. was supported in part by the European Community Net-work ENRAGE (grant MRTN-CT-2004-005616), and by the Agence Nationale de la Recherche (grantANR-06-BLAN-0124-03).
DS e-Archivo
RD 27 jul. 2024