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

Asekha Khantavchai, Thiradet Jiarasuksakun

Authors

  • Support Team

Keywords:

perfect matching, recurrence relation, linear chain graph, snake chain graph

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.

Downloads

Published

2017-12-01

How to Cite

Team, S. (2017). Using Recurrence Relation to Count a Number of Perfect Matching in Linear Chain and Snake Chain Graphs: Asekha Khantavchai, Thiradet Jiarasuksakun. Thai Journal of Mathematics, 15(3), 783–795. Retrieved from https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/718

Issue

Section

Articles