Publication:
Is the five-flow conjecture almost false?

dc.affiliation.dptoUC3M. Departamento de Matemáticases
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Modelización, Simulación Numérica y Matemática Industriales
dc.contributor.authorJacobsen, Jesper Lykke
dc.contributor.authorSalas Martínez, Jesús
dc.contributor.funderMinisterio de Economía y Competitividad (España)es
dc.date.accessioned2021-07-12T09:58:00Z
dc.date.available2021-07-12T09:58:00Z
dc.date.issued2013-07
dc.description.abstractThe 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→∞es
dc.description.sponsorshipThe 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).en
dc.format.extent34
dc.identifier.bibliographicCitationJacobsen, J. L. & Salas, J. (2013). Is the five-flow conjecture almost false? Journal of Combinatorial Theory, Series B, 103(4), pp. 532–565.en
dc.identifier.doihttps://doi.org/10.1016/j.jctb.2013.06.001
dc.identifier.issn0095-8956
dc.identifier.publicationfirstpage532
dc.identifier.publicationissue4
dc.identifier.publicationlastpage565
dc.identifier.publicationtitleJournal of Combinatorial Theory, Series Bes
dc.identifier.publicationvolume103es
dc.identifier.urihttps://hdl.handle.net/10016/33034
dc.identifier.uxxiAR/0000013762
dc.language.isoeng
dc.publisherElsevieren
dc.relation.projectIDGobierno de España. MTM2008-03020es
dc.relation.projectIDGobierno de España. FPA2009-08785es
dc.relation.projectIDGobierno de España. MTM2011-24097es
dc.relation.projectIDGobierno de España. FIS2012-34379es
dc.rights© 2013 Elsevier Inc.en
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España*
dc.rights.accessRightsopen accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subject.ecienciaIngeniería Industriales
dc.subject.ecienciaMatemáticases
dc.subject.otherNowhere zero flowsen
dc.subject.otherFlow polynomialen
dc.subject.otherFlow rootsen
dc.subject.otherTutte's five-flow conjectureen
dc.subject.otherPetersen graphen
dc.subject.otherTransfer matrixen
dc.titleIs the five-flow conjecture almost false?en
dc.typeresearch article*
dc.type.hasVersionAM*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Five-flow_JCT(SB)_2013_ps.pdf
Size:
721.22 KB
Format:
Adobe Portable Document Format