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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.243--258
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980771
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:59
Dernière modification le : jeudi 7 septembre 2017 - 01:03:48
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:33:30

Fichier

2363-8315-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

806

Téléchargements de fichiers

384