On the Maximum Number of Maximum Independent Sets of Bipartite Graphs

期刊论文
发表日期：

2024年5月23日

查看全文

Wanting Sun,
Shuchao Li

摘要

An independent set in a graph G is a set of pairwise nonadjacent vertices of G. The independence number, $\alpha $ $α$ , of G is the maximum cardinality of an independent set in G. An independent set in G is maximum if it has cardinality $\alpha $ $α$ . Mohr and Rautenbach determined the n-vertex trees (resp. connected graphs, disconnected graphs) with independence number $\alpha $ $α$ having the largest number of maximum independent sets. As a continuance of these works, we give complete characterizations among the following families of graphs:

the n-vertex forests with independence number $\alpha $ $α$ having the first three largest number of maximum independent sets;

the n-vertex trees with independence number $\alpha $ $α$ having the second and third largest number of maximum independent sets;

the bipartite graphs (containing at least one cycle) of order n and independence number $\alpha $ $α$ having the maximum number of maximum independent sets;

the disconnected n-vertex graphs with independence number $\alpha $ $α$ having the second largest number of maximum independent sets.

Furthermore, we obtain a complete classification of connected graphs with order n and independence number $n-3$

n - 3

, which gives a solution to an open problem of Derikvand and Oboudi.