The thesis examines the counting of matchings in graphs, focusing on their application in chemical graph theory, where matchings correspond to the Kekulé structures of molecules and determine their aromatic stability. The primary objective is the calculation of the Hosoya index, a molecular descriptor that encodes structural information relevant to the physicochemical properties of compounds. Since counting matchings in general graphs is computationally hard, as the problem of counting perfect matchings (and consequently general $k$-matchings) belongs to the class of #P-complete problems, the work focuses on specific graph classes. Using efficient methods, among which the transfer matrix method plays a central role, the Hosoya index for these classes can be computed in polynomial time. Through recursive relations, these methods enable calculation of the Hosoya index for complex graphs, such as benzenoid and coronoid chains, cyclic systems, and successively amalgamated graphs.
|
