EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minimum Maximal Matchings in Phenylene Chains

Kai Deng, Ying Zhao, Xianyue Li

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →