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 条
[51]  
WU FY, 1976, J MATH PHYS, V17, P439, DOI 10.1063/1.522914
[52]   POTTS-MODEL AND GRAPH-THEORY [J].
WU, FY .
JOURNAL OF STATISTICAL PHYSICS, 1988, 52 (1-2) :99-112
[53]  
Zhang C. - Q., 1997, INTEGER FLOWS CYCLE