Skip to Main content Skip to Navigation
Journal articles

Maximal independent sets in bipartite graphs with at least one cycle

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 \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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00980771
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, April 18, 2014 - 4:43:59 PM
Last modification on : Friday, September 11, 2020 - 2:54:32 PM
Long-term archiving on: : Monday, April 10, 2017 - 3:33:30 PM

File

2363-8315-2-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00980771, version 1

Collections

Citation

Shuchao Li, Huihui Zhang, Xiaoyan Zhang. Maximal independent sets in bipartite graphs with at least one cycle. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.243--258. ⟨hal-00980771⟩

Share

Metrics

Record views

851

Files downloads

1382