Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Weighted spanning trees on some self-similar graphs. | Weighted spanning trees on some self-similar graphs Daniele D Angeli Alfredo Donno Departamento de Matematicas Dipartimento di Matematica Universidad de los Andes Sapienza Universita di Roma Carrera 1 18A - 70 Bogota Colombia Piazzale A. Moro 2 00185 Roma Italia dangeli@ donno@ Submitted Aug 11 2010 Accepted Dec 20 2010 Published Jan 12 2011 Mathematics Subject Classification 05A15 05C22 20E08 05C25 Abstract We compute the complexity of two infinite families of finite graphs the Sierpinski graphs which are finite approximations of the well-known Sierpinski gasket and the Schreier graphs of the Hanoi Towers group H 3 acting on the rooted ternary tree. For both of them we study the weighted generating functions of the spanning trees associated with several natural labellings of the edge sets. 1 Introduction The enumeration of spanning trees in a finite graph is largely studied in the literature and it has many applications in several areas of Mathematics as Algebra Combinatorics Probability and of Theoretical Computer Science. Given a connected finite graph Y V Y E Y where V Y and E Y denote the vertex set and the edge set of Y respectively a spanning tree of Y is a subgraph of Y which is a tree and whose vertex set coincides with V Y . The number of spanning trees of a graph Y is called the complexity of Y and is denoted by T Y . The famous Kirchhoff s Matrix-Tree Theorem 1847 states that T Y is equal to the constant value of any cofactor of the Laplace matrix of Y which is obtained as the difference between the degree matrix of Y and its adjacency matrix. Equivalently T Y V Y is given by the product of all nonzero eigenvalues of the Laplace matrix of Y. It is interesting to study complexity when the system grows. More precisely given a sequence pn n 1 of finite graphs with complexity T rn such that V Yn X the limit log T Yn lim V Y H V Yn THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P16 1 when it exists is called the asymptotic .
