首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The Tutte Polynomial as a Growth Function
Authors:Norman Biggs
Institution:(1) Centre for Discrete and Applicable Mathematics, London School of Economics, Houghton Street, London, WC2A 2AE, UK
Abstract:The 'dollar game' represents a kind of diffusion process on a graph. Under the rules of the game some cofigurations are both stable and recurrent, and these are known as critical cofigurations. The set of critical configurations can be given the structure of an abelian group, and it turns out that the order of the group is the tree-number of the graph. Each critical configuration can be assigned a positive weight, and the generating function that enumerates critical configurations according to weight is a partial evaluation of the Tutte polynomial of the graph. It is shown that the weight enumerator can also be interpreted as a growth function, which leads to the conclusion that the (partial) Tutte polynomial itself is a growth function.
Keywords:Tutte polynomial  chip-firing  critical group  growth function
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号