欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Tutte polynomial of an Eulerian graph
时间  Datetime
2018-12-07 13:30 — 14:30 
地点  Venue
Middle Lecture Room
报告人  Speaker
Jun Ma (马俊)
单位  Affiliation
Shanghai Jiao Tong University
邀请人  Host
Yaokun Wu
报告摘要  Abstract

William Tutte is one of the founders of modern graph theory. For every undirected graph G, Tutte defined a two-variables polynomial TG(x,y) which plays an important role in graph theory. It encodes information about subgraphs of G. For example, for a connected graph G, TG(1,1) is the number of spanning trees of G, TG(2,1) is the number of spanning forests of G, TG(1,2) is the number of connected spanning subgraphs of G, TG(2,2) is the number of spanning subgraphs of G.

One has been looking for analogues of the Tutte polynomial for digraphs for a long time. Recently, considering the chip-firing game on an Eulerian digraph, Kévin PerrotTrung Van Pham and Swee Hong Chan gave generalizations of the partial Tutte polynomial TG(1,y) from the point of view of recurrent con?gurations of the chip-?ring game.

In this talk, we let D be an weak-connected Eulerian digraph and v be a vertex of D. We will introduce two polynomials PD,v(y) and QD,v(y), which are defined on the set of v-sink subgaphs and the set of acyclic v-sink subgaphs of D, respectively. We find that these two polynomials have very good invariance properties. In particular, these two polynomials are independent of the choice of the vertex v. Moreover, we will introduce two polynomials P~D,v(y) and Q~D,v(y), which are defined on the set of v-source subgaphs and the set of acyclic v-source subgaphs of D, respectively. We prove that PD,v(y)=P~D,v(y) and QD,v(y)=Q~D,v(y). For these reasons, we simply write PD,v(y) and&am