A Study on the Hosoya Index and Matching Structures in Certain Graph Families

Abstract

     Hosoya index, that is, the total number of matchings in a graph, is an important invariant in enumerative and chemical graph theory. As a counting parameter associated with the combinatorial structure of independent edge set, it is central to the study of molecular stability, branching patterns and structural complexity in chemical graph models as well as purely combinatorial studies of matching behavior. In this work we formulate a unified and systematic approach for the calculation of Hosoya index among families of structured graphs. Our approach combines vertex- and edge-decomposition identities, recurrence relations following local structural constraints, and transfer-like state methods to treat recurring or compositional configurations. By means of said approach, we obtain explicit formulae and closed-form expressions for classical families of graphs such as paths and cycles, allowing one to recover both Fibonacci- and Lucas-type behaviours stemming from the linear and cyclic growth patterns. We also consider graph families defined by classical structural extensions that are limited in size, such as path-based constructions (Family A), cycle-based graphs with extra edges (Family B) and modular core–attachment structures (Family C). For these families, we show how the local matching constraints translate into global enumeration patterns and show for example, how structural features like a cycle or pendant components systematically impose the growth rate of. Computational experiments are presented to verify the theoretical results and test on small instances either with recurrence-based implementations or direct enumeration. The conclusions endorse the validity of the obtained formulae and reveal harmonized growth pattern depending on matching structure than superficial topological differences.