The K-induced Matching Number And Total Induced Matching Number For Graphs

In matching theory,the matching counting of graphs is an important combinatorial counting problem,mainly involving the k-matching counting and full matching counting of graphs,etc.The Japanese chemist Haruo Hosoya found that the total matching number of the graph,also known as the Hosoya index of the graph,is closely related to the physical properties such as the boiling point of the substance and the chemical structure and calculation of the substance,and also revealed the applicability of the Hosoya index in the theory of conjugated π-electronic system.For a matching M of the graph G,if the vertex induced subgraph V(M)of M is a 1-regular subgraph,then M is called an induced matching of G.Induced matching belongs to generalized matching and has certain applications in communication network testing,concurrent transmission of information in wireless self-organizing networks,and secure communication channels in broadcast networks.The induced matching counting problem is a natural extension of the matching counting problem and has important theoretical research value.The number of induced matching exactly containing k edges in a graph is called the k-induced matching number of the graph,and the total induced matching number of the graph is the number of all induced matchings of the graph.Recently,Yan Liu et al.(2021)used FibonacciNarayana sequence to study the counting problem of the total induced matching number of a graph,and obtained some order relations about the total induced matching number with the help of graph transformation,and characterized the corresponding extreme graphs.In this article,a new graph invariant about induced matching countinginduced matching polynomial is defined.Some properties of the induced matching polynomial are given and the induced matching polynomials of some classical graph classes are also obtained.In addition,the recursive relations of the k-induced matching number under graph operations of edge deletion and vertex deletion are given respectively,and the k-induced matching counting problem of a given diameter tree and the total induced matching counting problem of several types of recursive trees are solved.At last,the problem of total induced matching counting of genetic graphs is discussed,and the formula of total induced matching counting of genetic graphs is given with the help of graph transformation.As an application,the formulas of total induced matching counting of quadrangular and hexagonal chains are determined,and the corresponding extreme graphs are described.