WCSE 2022
ISBN: 978-981-18-3959-7 DOI: 10.18178/wcse.2022.06.040

Counting the Total Induced Matchings for Recursive Trees

Caicuozhuoma Xie, Haizhen Ren

Abstract— An induced matching of the graph G is a matching which forms an induced subgraph of 1- regular in G. Induced matching is widely used in computer networks, such as communication network testing, concurrent transmission of messages, secure communication channels etc. Counting problem on the total number of induced matchings was introduced by Liu et al.(2021). In view of its computational difficulty, the total number of induced matchings for restricted graph is therefore of interest. By combination method and characteristic equation we get the closed formulas of the total number of induced matchings for some recursive trees.

Index Terms—Induced matching, recursive tree, the total number of induced matchings

Caicuozhuoma Xie
School of Mathematics and Statistics, Qinghai Normal University, Xining, CHINA
Haizhen Ren School of Mathematics and Statistics, Qinghai Normal University, Xining, CHINA
Academy of Plateau, Science and Sustainability, Xining, CHINA
The State Key Laboratory of Tibetan Information Processing and Application, Xining, CHINA

[Download]


Cite:Caicuozhuoma Xie, Haizhen Ren, "Counting the Total Induced Matchings for Recursive Trees, " Proceedings of 2022 the 12th International Workshop on Computer Science and Engineering (WCSE 2022), pp. 280-284, June 24-27, 2022.