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

An \textit{independent set} in a graph comprises vertices that are not adjacent to one another, whereas a \textit{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(G)=n$, the cardinality of a maximum independent set in $G$ is $\alpha(G)-\alpha$, the size of the largest clique in $G$ is $\omega(G)=\omega$, the cardinality of the intersection of all maximum independent sets in $G$ is $\xi(G)=\xi$. As the main finding of the article, we present an upper bound on the number of maximum independent sets as follows: \[ s_{\alpha} \leq \sum_{k=0}^{\alpha- \xi} \binom{n - \alpha - \omega + 1}{k} + (\omega - 1) \cdot \sum_{k=0}^{\alpha- \xi - 1} \binom{n - \alpha - \omega + 1}{k} \] \[ \leq \omega \cdot 2^{\min(\alpha - \xi, n - \alpha - \omega - \xi + 1)}. \] As an application of our findings, we explore a series of inequalities that connect the number of longest increasing subsequences with the number of longest decreasing subsequences in a given sequence of integers.