Density of Real Zeros of the Tutte Polynomial

被引:0
作者
Ok, Seongmin [1 ]
Perrett, Thomas J. [2 ]
机构
[1] Korea Inst Adv Study, Sch Computat Sci, Seoul 02455, South Korea
[2] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark
基金
新加坡国家研究基金会;
关键词
CHROMATIC ROOTS; INAPPROXIMABILITY; COMPLEXITY; GRAPHS; PLANE;
D O I
10.1017/S0963548318000019
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The Tutte polynomial of a graph is a two-variable polynomial whose zeros and evaluations encode many interesting properties of the graph. In this article we investigate the real zeros of the Tutte polynomials of graphs, and show that they form a dense subset of certain regions of the plane. This is the first density result for the real zeros of the Tutte polynomial in a region of positive volume. Our result almost confirms a conjecture of Jackson and Sokal except for one region which is related to an open problem on flow polynomials.
引用
收藏
页码:398 / 410
页数:13
相关论文
共 44 条
  • [11] Tutte Polynomial of Scale-Free Networks
    Chen, Hanlin
    Deng, Hanyuan
    JOURNAL OF STATISTICAL PHYSICS, 2016, 163 (04) : 714 - 732
  • [12] Preface: Old and New Perspectives on the Tutte Polynomial
    Joseph P. S. Kung
    Annals of Combinatorics, 2008, 12 : 133 - 137
  • [13] Preface: Old and new perspectives on the Tutte polynomial
    Kung, Joseph P. S.
    ANNALS OF COMBINATORICS, 2008, 12 (02) : 133 - 137
  • [14] Tutte Polynomial in Functional Magnetic Resonance Imaging
    Garcia Castrillon, Marlly Veronica
    APPLICATIONS OF DIGITAL IMAGE PROCESSING XXXVIII, 2015, 9599
  • [15] Tutte polynomial of a small-world Farey graph
    Liao, Yunhua
    Hou, Yaoping
    Shen, Xiaoling
    EPL, 2013, 104 (03)
  • [16] Formulas for the computation of the Tutte polynomial of graphs with parallel classes
    Mphako-Banda, Eunice
    Allagan, Julian A.
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2018, 6 (01) : 113 - 122
  • [17] On the Tutte-Krushkal-Renardy polynomial for cell complexes
    Bajo, Carlos
    Burdick, Bradley
    Chmutov, Sergei
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2014, 123 (01) : 186 - 201
  • [18] A recipe theorem for the topological Tutte polynomial of Bollobas and Riordan
    Ellis-Monaghan, Joanna A.
    Sarmiento, Irasema
    EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (06) : 782 - 794
  • [19] Chromatic polynomials of planar triangulations, the Tutte upper bound and chromatic zeros
    Shrock, Robert
    Xu, Yan
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2012, 45 (05)
  • [20] A Tutte polynomial for maps II: The non-orientable case
    Goodall, Andrew
    Litjens, Bart
    Regts, Guus
    Vena, Lluis
    EUROPEAN JOURNAL OF COMBINATORICS, 2020, 86