2018/05/07 by Mohr, Elena, Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1805.02519
We give a very short and simple proof of Zykov's generalization of Turán's theorem, which implies that the number of maximum independent sets of a graph of order n and independence number α with αn, and we also characterize the extremal graphs. Finally, we show that the number of maximum independent sets of a subcubic tree of order n and independence number α is at most ((1+√(5))/(2))2n-3α+1, and we provide more precise results for extremal values of α.