Tutte polynomial and G-parking functions

الأصل · EN

Let G be a connected graph with vertex set {0,1,2,...,n}. We allow G to have multiple edges and loops. In this paper, we give a characterization of external activity by some parameters of G-parking functions. In particular, we give the definition of the bridge vertex of a G-parking function and obtain an expression of the Tutte polynomial TG(x,y) of G in terms of G-parking functions. We find the Tutte polynomial enumerates the G-parking function by the number of the bridge vertices.