tailieunhanh - Báo cáo toán học: "The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph. | The number of 0-1-2 increasing trees as two different evaluations of the Tutte polynomial of a complete graph C. Merino Institute de Matemáticas Universidad Nacional Autánoma de Máxico Circuito Exterior . Coyoacán 04510 Máxico . merino@ Submitted Nov 21 2007 Accepted Jul 11 2008 Published Jul 21 2008 Mathematics Subject Classifications 05A19 Abstract If Tn x y is the Tutte polynomial of the complete graph Kn we have the equality Tra 1 1 0 Tn 2 0 . This has an almost trivial proof with the right combinatorial interpretation of Tn 1 0 and Tn 2 0 . We present an algebraic proof of a result with the same flavour as the latter Tn 2 1 1 Tn 2 1 where Tn 1 1 has the combinatorial interpretation of being the number of 0-1-2 increasing trees on n vertices. 1 Introduction Given a graph G V E we define the rank function of G r P E Z as r A VI k A for A c E where k A is the number of connected components in the graph V A . The 2-variable graph polynomial T G X y known as the Tutte polynomial of G is defined as T G x y x - 1 r E -IA y - i IAI-r A 1 ACE The Tutte polynomial of G has many interesting combinatorial interpretations when evaluated on different points X y and along several algebraic curves. One that is particularly interesting is along the line x 1 which can be interpreted as the generating function of critical configuration of the sandpile model see 8 or as the generating function of the G-parking functions see 9 . When the graph G is the complete graph on n vertices Kn the latter is the classical generating function of parking functions or the inversion enumerator of labelled trees on n vertices see 10 . In the following section we prove the main theorem of the paper Supported by Conacyt of Mexico. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N28 1 Theorem 1. T Kn 2 -1 T Kn 2-1 -1 . The last section shows how this result is related to the number of 0-1-2 increasing trees on n vertices. 2 T Kn 2 -1 and T Kn 2 1 -1 Let us assume that the vertices