Shuchao Li ; Huihui Zhang ; Xiaoyan Zhang - Maximal independent sets in bipartite graphs with at least one cycle

dmtcs:607 - Discrete Mathematics & Theoretical Computer Science, September 9, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.607
Maximal independent sets in bipartite graphs with at least one cycleArticle

Authors: Shuchao Li 1; Huihui Zhang 1; Xiaoyan Zhang 2

  • 1 Faculty of Mathematics and Statistics [Wuhan]
  • 2 School of Mathematical Science & Institute of Mathematics [Nanjing]

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 \mathscrBₙ (resp. \mathscrBₙ') 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 \mathscrBₙ (resp. \mathscrBₙ') is considered. Among \mathscrBₙ the disconnected graphs with the first-, second-, \ldots, \fracn-22-th largest number of maximal independent sets are characterized, while the connected graphs in \mathscrBₙ having the largest, the second largest number of maximal independent sets are determined. Among \mathscrBₙ' graphs have the largest number of maximal independent sets are identified.


Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: September 9, 2013
Accepted on: June 9, 2015
Submitted on: April 18, 2013
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 373 times.
This article's PDF has been downloaded 446 times.