ISBN: 978-981-18-3959-7 DOI: 10.18178/wcse.2022.06.040
Counting the Total Induced Matchings for Recursive Trees
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
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.