Logo

Download

Title:
Counting Matchings in Caterpillar Graphs with an Application to a Class of Benzenoid Chains
Authors:
Hülya Buksur Köleli ORCID iD 0009-0003-0466-5886
Bünyamin Şahin ORCID iD 0000-0003-1094-5481
Volume
97
Issue
1
Year
2027
Pages
243-257
Abstract

Total number of matchings is called Hosoya index in graph theory. Although Hosoya index was introduced in 1971, the relations between the Hosoya index of caterpillar graphs and Euler’s continuants were introduced in 2007. In this paper, we show that the Hosoya index of caterpillar graphs can be computed as product of \( 2 \times 2 \) matrices. Moreover, we obtain that Hosoya index of the caterpillar graphs \( Z(C_n (x,\dots,x)) \) equals to \( (n+1)-th \) Fibonacci polynomial and we show that the Hosoya index of the caterpillar graphs \( Z(C_n (x+1,\dots,x+1)) \) can be shown in a polynomial form with the coefficients as a Pell triangle of Reference number A038137 in OEIS. Finally, we use these relations in the computation of the Kekulé number of a class \( \mathcal{H}_{n,x} \) of benzenoid chains which have n segments of length \( x \).