Maximal and maximum induced matchings in connected graphs

Bo-Jun Yuan, Zhao-Yu Yang, Lu Zheng and Shi-Cai Gong

Applied Mathematics and Computation, 2025, vol. 500, issue C

Abstract: An induced matching is defined as a set of edges whose end-vertices induce a subgraph that is 1-regular. Building upon the work of Gupta et al. (2012) [11] and Basavaraju et al. (2016) [1], who determined the maximum number of maximal induced matchings in general and triangle-free graphs respectively, this paper extends their findings to connected graphs with n vertices. We establish a tight upper bound on the number of maximal and maximum induced matchings, as detailed below:{(n2)if1≤n≤8;(⌊n2⌋2)⋅(⌈n2⌉2)−(⌊n2⌋−1)⋅(⌈n2⌉−1)+1if9≤n≤13;10n−15+n+14430⋅6n−65if14≤n≤30;10n−15+n−15⋅6n−65ifn≥31. This result not only provides a theoretical upper bound but also implies a practical algorithmic application: enumerating all maximal induced matchings of an n-vertex connected graph in time O(1.5849n). Additionally, our work offers an estimate for the number of maximal dissociation sets in connected graphs with n vertices.

Keywords: Matching; Maximum induced matching; Maximal induced matching; Upper bound; Block (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325001596
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:500:y:2025:i:c:s0096300325001596

DOI: 10.1016/j.amc.2025.129432

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().