Is the five-flow conjecture almost false?

被引:10
作者
Jacobsen, Jesper Lykke [1 ,2 ]
Salas, Jesus [3 ,4 ]
机构
[1] Ecole Normale Super, Phys Theor Lab, F-75231 Paris, France
[2] Univ Paris 06, F-75252 Paris, France
[3] Univ Carlos III Madrid, Grp Modelizac Simulac Numer & Matemat Ind, Leganes 28911, Spain
[4] Univ Carlos III Madrid, Inst Gregorio Millan, Grp Teorias Campos & Fis Estadist, Unidad Asociada IEM CSIC, Madrid, Spain
基金
美国国家科学基金会;
关键词
Nowhere zero flows; Flow polynomial; Flow roots; Tutte's five-flow conjecture; Petersen graph; Transfer matrix; MODEL PARTITION-FUNCTIONS; POTTS-MODEL; CHROMATIC ROOTS; ZEROS; POLYNOMIALS; LIMITS; GRAPH;
D O I
10.1016/j.jctb.2013.06.001
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:532 / 565
页数:34
相关论文
共 53 条
[1]  
[Anonymous], NUMERICAL COMPUTATIO
[2]  
[Anonymous], 1994, FDN COMPUTER SCI
[3]   EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].
APPEL, K ;
HAKEN, W .
ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490
[4]   A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings [J].
Bedini, Andrea ;
Jacobsen, Jesper Lykke .
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2010, 43 (38)
[5]   IS THE 4-COLOR CONJECTURE ALMOST FALSE [J].
BERAHA, S ;
KAHANE, J .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (01) :1-12
[6]   LIMITS OF ZEROS OF RECURSIVELY DEFINED POLYNOMIALS [J].
BERAHA, S ;
KAHANE, J ;
WEISS, NJ .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1975, 72 (11) :4209-4209
[7]   LIMITS OF CHROMATIC ZEROS OF SOME FAMILIES OF MAPS [J].
BERAHA, S ;
KAHANE, J ;
WEISS, NJ .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (01) :52-65
[8]  
Beraha S., 1978, Advances in Mathematics, Supplementary Studies, V1, P213
[9]   Design, analysis, and implementation of a multiprecision polynomial rootfinder [J].
Bini, DA ;
Fiorentino, G .
NUMERICAL ALGORITHMS, 2000, 23 (2-3) :127-173
[10]   CHROMATIC POLYNOMIALS [J].
BIRKHOFF, GD ;
LEWIS, DC .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 60 (NOV) :355-451