Counting Matchings in Caterpillar Graphs with an Application to a Class of Benzenoid Chains

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 × 2 matrices. Moreover, we obtain that Hosoya index of the caterpillar graphs Z(Cn(x, …, x)) equals to (n + 1) − th Fibonacci polynomial and we show that the Hosoya index of the caterpillar graphs Z(Cn(x + 1, …, 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 Hn,x of benzenoid chains which have n segments of length x.