×

Using recurrence relation to count a number of perfect matching in linear chain and snake chain graphs. (English) Zbl 1441.05184

Summary: This paper presents the recurrence relation using to count a number of perfect matchings in linear chain and snake chain graphs. These graphs are offen found in the chemical structure. A perfect matching graph \(M\) is a subgraph of \(G\) where there are no edges in \(M\) adjacent to each other and \(V(M)=V(G)\). \(\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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
11B37 Recurrences