tailieunhanh - Báo cáo toán hoc:" Almost all trees have an even number of independent sets "

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í toán học quốc tế đề tài: Almost all trees have an even number of independent sets. | Almost all trees have an even number of independent sets Stephan G. Wagner Department of Mathematical Sciences Stellenbosch University Private Bag X1 Matieland 7602 South Africa swagner@ Submitted Mar 28 2009 Accepted Jul 21 2009 Published Jul 31 2009 Mathematics Subject Classifications 05C30 05A16 05C05 05C69 Abstract This paper is devoted to the proof of the surprising fact that almost all trees have an even number of independent vertex subsets in the sense that the proportion of those trees with an odd number of independent sets tends to 0 as the number of vertices approaches to and to its generalisation to other moduli for fixed m the probability that a randomly chosen tree on n vertices has a number of independent subsets that is divisible by m tends to 1 as n to. 1 Introduction The number of independent vertex subsets is one of many interesting graph parameters that have been studied in the past. It was introduced to the mathematical literature in a paper by Prodinger and Tichy in 1982 21 where it was shown amongst other things such as explicit formula for various classes of graphs that the star and the path maximize resp. minimize the number of independent sets among all trees of given size. In subsequent works Kirschenhofer Prodinger and Tichy 11 12 investigated the average number of independent sets in certain classes of rooted trees such as binary trees providing some nice combinatorial results. Generally the number of independent sets is a parameter that is particularly well-studied for trees and tree-like structures forests unicyclic graphs etc. a paper of Lin and Lin 15 extends the aforementioned results and in recent years a wealth of literature on the so-called extremal problem given a class of graphs determine those members of the class that maximize or minimize the number of independent sets has developed see for instance 9 14 19 20 23 for some nice results in this direction. Part of the interest is due to the fact that this parameter .