Tutte Polynomial of Scale-Free Networks
Tutte Polynomial of Scale-Free Networks
复制标题
无标度网络的 Tutte 多项式
DOI：
10.1007/s10955-016-1465-4
复制
发表时间：
2016-03
影响因子：
1.6
通讯作者：
Hanyuan Deng
中科院分区：
文献类型：
--
作者：
Hanlin Chen;Hanyuan Deng
图的 Tutte 多项式，或者等效的 q 状态 Potts 模型配分函数，是一个二变量多项式图不变量，在统计物理学和组合学中都具有相当重要的意义。图的这个不变量的计算通常是 NP 困难的。在本文中，我们重点关注两个迭代增长的无标度网络，它们在现实系统中普遍存在。基于它们的自相似结构，我们主要得到两个无标度网络（格）的Tutte多项式的递推公式，一个是分形的“大世界”，另一个是非分形的但具有小世界性质。此外，我们给出了(x,y)平面上几个特殊点的Tutte多项式的精确解析表达式，例如生成树的数量、非循环方向的数量等。
The Tutte polynomial of a graph, or equivalently theq-state Potts model partition function, is a two-variable polynomial graph invariant of considerable importance in both statistical physics and combinatorics. The computation of this invariant for a graph is NP-hard in general. In this paper, we focus on two iteratively growing scale-free networks, which are ubiquitous in real-life systems. Based on their self-similar structures, we mainly obtain recursive formulas for the Tutte polynomials of two scale-free networks (lattices), one is fractal and “large world”, while the other is non-fractal but possess the small-world property. Furthermore, we give some exact analytical expressions of the Tutte polynomial for several special points at (x,y)-plane, such as, the number of spanning trees, the number of acyclic orientations, etc.
登录
查看更多内容
影响因子：
2.4
作者：
Dorogovtsev, SN;Goltsev, AV;Mendes, JFF
通讯作者：
Mendes, JFF
DOI：
10.1016/s0378-4371(02)00977-9
发表时间：
2001-11
影响因子：
3.3
作者：
Shu-Chiuan Chang
通讯作者：
Shu-Chiuan Chang
DOI：
10.1016/s0378-4371(00)00109-6
发表时间：
2000-01
影响因子：
3.3
作者：
R. Shrock
通讯作者：
R. Shrock
影响因子：
44.1
作者：
F. Y. Wu
通讯作者：
F. Y. Wu
DOI：
10.1016/j.physa.2011.08.007
发表时间：
2012-02
影响因子：
3.3
作者：
Zhongzhi Zhang;Y. Sheng;Qiang Jiang
通讯作者：
Zhongzhi Zhang;Y. Sheng;Qiang Jiang