Using Recurrence Relation to Count a Number of Perfect Matching in Linear Chain and Snake Chain Graphs

Asekha Khantavchai, Thiradet Jiarasuksakun

Abstract

This paper presents the recurrence relation used to count a number of perfect matchings in linear chain and snake chain graphs. These graphs are offen found in the chemical structure. A matching graph M is a subgraph of a graph G where there are no edges adjacent to each other. If V(M)=V(G), we call M a “perfect matching”. phi(G) is a number of perfect matching of G which leads to important chemical properties.

The results show that a number of perfect matching of a linear chain graph depends on parity of faces and number of edges in each face. A number of perfect matching of a snake chain graph depends on parity of the chain.