Using recurrence relation to count a number of perfect matching in linear chain and snake chain graphs

Journal article

Authors/Editors

Strategic Research Themes

No matching items found.

Publication Details

Author list: Khantavchai A., Jiarasuksakun T.

Publication year: 2017

Journal: Thai Journal of Mathematics (1686-0209)

Volume number: 15

Issue number: 3

Start page: 783

End page: 795

Number of pages: 13

ISSN: 1686-0209

URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85041942073&partnerID=40&md5=1d831ae6436dcde8d62ef64bfa84d631

Languages: English-Great Britain (EN-GB)

View in Web of Science | View citing articles in Web of Science

Abstract

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). φ(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. © 2017 by the Mathematical Association of Thailand. All rights reserved.

Keywords

Linear chain graph, Perfect matching, Recurrence relation, Snake chain graph