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

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.*