New Upper Bounds on the Number of Maximum Independent Sets in a Graph

An independent set in a graph comprises vertices that are not adjacent to one another, whereas a clique consists of vertices where all pairs are adjacent. For a given graph G, let the following notations be defined: the number of vertices in G is n, the cardinality of a maximum independent set in G is α, the size of the largest clique in G is ω, the cardinality of the intersection of all maximum independent sets in G is ξ, and the number of maximum independent sets in G is sα. As the main finding of this article, we present an upper bound on the number of maximum independent sets as follows: sα≤ω·2n−α−ω+1,ifn−α−ω+1≤α−ξ−1;n−α−ω+1α−ξ+ω·∑k=0α−ξ−1n−α−ω+1k,ifn−α−ω+1≥α−ξ.. As an application of our findings, we explore a series of inequalities that connects the number of longest increasing subsequences with the number of longest decreasing subsequences in a given sequence of integers.