Counting Perfect Matchings in Chain Graphs with the Specific Colored Faces

被引：0

作者：

Saduakdee, Supaporn ^{[1
]}

Maliwan, Pattana ^{[2
]}

Singthong, Thitaporn ^{[2
]}

Sirilap, Supatta ^{[2
]}

Khemmani, Varanoot ^{[2
]}

机构：

[1] Chandrakasem Rajabhat Univ, Fac Sci, Program Math, Bangkok 10900, Thailand

[2] Srinakharinwirot Univ, Dept Math, Fac Sci, Bangkok 10110, Thailand

来源：

INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE | 2024年 / 19卷 / 03期

关键词：

Matching; perfect matching; chain graph; snake chain graph; recurrence relation; NUMBER;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we study counting perfect matchings in linear chain graphs, focusing on identically colored and alternatingly colored odd faces, using recurrence relations. Our primary objective is to derive explicit formulas for the numbers of perfect matchings in linear chain graphs with identically colored odd faces. Furthermore, we establish a relationship between the numbers of perfect matchings in linear chain graphs with identically colored odd faces and strip snake chain graphs. This relationship provides us with an alternative way of validating the numbers of perfect matchings in linear chain graphs with the same colored odd faces.

引用

页码：677 / 686

页数：10

共 10 条

[1] Cai J. Y., 2020, 47 INT C AUTOMATA LA, V168
[2] On the number of perfect matchings of line graphs
Dong, Fengming
Yan, Weigen
Zhang, Fuji
[J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (06) : 794 - 801
[3] Scaling matrices and counting the perfect matchings in graphs
Dufosse, Fanny
Kaya, Kamer
Panagiotas, Ioannis
Ucar, Bora
[J]. DISCRETE APPLIED MATHEMATICS, 2022, 308 : 130 - 146
[4] COUNTING PERFECT MATCHINGS AND THE SWITCH CHAIN
Dyer, Martin
Muller, Haiko
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1146 - 1174
[5] Ebrahimnejad F., 2022, 13 INNOVATIONS THEOR, V61, P1
[6] Khantavchai A, 2017, THAI J MATH, V15, P783
[7] Marandi A, 2014, IRAN J MATH CHEM, V5, pS27
[8] Okamoto Y, 2010, LECT NOTES COMPUT SC, V5911, P296, DOI 10.1007/978-3-642-11409-0_26
[9] Counting the maximal and perfect matchings in benzenoid chains
Shi, Lingjuan
Deng, Kai
[J]. APPLIED MATHEMATICS AND COMPUTATION, 2023, 447
[10] On Counting Perfect Matchings in General Graphs
Stefankovic, Daniel
Vigoda, Eric
Wilmes, John
[J]. LATIN 2018: THEORETICAL INFORMATICS, 2018, 10807 : 873 - 885

← 1 →