Discrete Mathematics & Theoretical Computer Science, Vol 15, No 2 (2013)

Font Size:  Small  Medium  Large

Maximal independent sets in bipartite graphs with at least one cycle

Shuchao LI, Huihui Zhang, Xiaoyan Zhang

Abstract


A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all $n$-vertex bipartite graphs. The corresponding extremal graphs are forests. It is natural and interesting for us to consider this problem on bipartite graphs with cycles. Let $\mathscr{B}_n$ (resp. $\mathscr{B}_n'$) be the set of all $n$-vertex bipartite graphs with at least one cycle for even (resp. odd) $n$. In this paper, the largest number of maximal independent sets of graphs in $\mathscr{B}_n$ (resp. $\mathscr{B}_n'$) is considered. Among $\mathscr{B}_n$ the disconnected graphs with the first-, second-, $\ldots, \frac{n-2}{2}$-th largest number of maximal independent sets are characterized, while the connected graphs in $\mathscr{B}_n$ having the largest, the second largest number of maximal independent sets are determined. Among $\mathscr{B}_n'$ graphs have the largest number of maximal independent sets are identified.

Full Text: PDF PostScript