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.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


The Thai Journal of Mathematics organized and supported by The Mathematical Association of Thailand and Thailand Research Council and the Center for Promotion of Mathematical Research of Thailand (CEPMART).

Copyright 2020 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|