Minimum Maximal Matchings in Phenylene Chains
Match Communications in Mathematical and in Computer Chemistry · 12.03.2026 · 3 (96) · 997
DOI: 10.46793/match.96-3.33925 ↗Kurz gefasst
Fachartikel in der Zeitschrift Match Communications in Mathematical and in Computer Chemistry, online erschienen am 12.03.2026. Verfasst von Kai Deng und 2 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: North Minzu University Graduate Innovation Project.
Abstract (Originalsprache)
A matching M in a graph G is a set of pairwise non-adjacent edges. M is maximal if it is not contained in any other matching of G. A minimum maximal matching is a maximal matching of minimum size, and its cardinality is the saturation number of G. Maximal matchings serve as an effective model for characterizing certain real-world problems, while the saturation number captures information about their worst-case scenarios in a certain sense. In this paper, we prove that the saturation number of any phenylene chain with n benzenoids is 2n. We also derive a formula to enumerate minimum maximal matchings via the transfer matrix method. Furthermore, we determine the extremal phenylene chains with n benzenoids achieving the largest and smallest number of minimum maximal matchings, respectively.
Förderung
- North Minzu University Graduate Innovation Project
Zitieren
APA
Deng, K., Zhao, Y., & Li, X. (2026). Minimum Maximal Matchings in Phenylene Chains. Match Communications in Mathematical and in Computer Chemistry, 3(96), 997. https://doi.org/10.46793/match.96-3.33925
Vancouver
Deng K, Zhao Y, Li X. Minimum Maximal Matchings in Phenylene Chains. Match Communications in Mathematical and in Computer Chemistry. 2026;3(96):997. doi:10.46793/match.96-3.33925
BibTeX
@article{Deng2026,
author = {Deng, Kai and Zhao, Ying and Li, Xianyue},
title = {Minimum Maximal Matchings in Phenylene Chains},
journal = {Match Communications in Mathematical and in Computer Chemistry},
year = {2026},
volume = {3},
number = {96},
pages = {997},
doi = {10.46793/match.96-3.33925}
}
EUVIMED