Enumerating the number of $k$-matchings in successively amalgamated graphs

Grad, Simon (author), Klavžar, Sandi (author)

In this paper, the transfer matrix technique using the $k$-matching vector is developed to compute the number of $k$-matchings in an arbitrary graph which can be constructed by successive amalgamations over sets of cardinality two. This widely extends known methods from the literature developed for computing the number of $k$-matchings in benzenoid chains, octagonal chains, cyclooctatetraene chains, and arbitrary cyclic chains. Two examples demonstrating how the present method can be applied are given, one of them being an elaborated chemical example.

• Language: English
• Keywords: matchings, transfer matrix, k-matching vector, chemical graphs, Toeplitz matrix
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.02.2026
• Year: 2026
• Number of pages: 9 str.
• Numbering: Vol. 510, art. no. 129703
• PID: 20.500.12556/RUL-175139
• UDC: 519.17
• ISSN on article: 0096-3003
• DOI: 10.1016/j.amc.2025.129703
• COBISS.SI-ID: 247009539
• Publication date in RUL: 17.10.2025

Record is a part of a journal

• Title: Applied mathematics and computation
• Shortened title: Appl. math. comput.
• Publisher: Elsevier
• ISSN: 0096-3003
• COBISS.SI-ID: 24983808

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: prirejanja, prehodne matrike, vektor k-prirejanj, kemijski grafi, Toeplitzova matrika