Evaluations of Tutte polynomials of regular graphs.

Let T G (x , y) be the Tutte polynomial of a graph G. In this paper we show that if (G n) n is a sequence of d -regular graphs with girth g (G n) → ∞ , then for x ≥ 1 and 0 ≤ y ≤ 1 we have lim n → ∞ ⁡ T G n (x , y) 1 / v (G n) = t d (x , y) , where t d (x , y) = { (d − 1) ( (d − 1) 2 (d − 1) 2 − x) d / 2 − 1 if x ≤ d − 1 and 0 ≤ y ≤ 1 , x (1 + 1 x − 1) d / 2 − 1 if x > d − 1 and 0 ≤ y ≤ 1. If (G n) n is a sequence of random d -regular graphs, then the same statement holds true asymptotically almost surely. This theorem generalizes results of McKay (x = 1 , y = 1 , spanning trees of random d -regular graphs) and Lyons (x = 1 , y = 1 , spanning trees of large-girth d -regular graphs). Interesting special cases are T G (2 , 1) counting the number of spanning forests, and T G (2 , 0) counting the number of acyclic orientations. [ABSTRACT FROM AUTHOR]