Research On Independent Sets And Matching Counting Of Some Graphs

The problem of independent sets and matching counting of graphs is a very important combinatorial counting problem.The independent set counting problem mainly studies the number of k-independent sets and the number of all independent sets of a graph.The number of all independent sets is called the Merrifield Simmons index(abbreviated as M-S index).The matching count problem is to study the number of k-matching and the number of all matching.The number of all matches is called the Hosoya index(abbreviated as H index).M-S index and H index are two common indexes in independent set and matching counting problems,and are also important molecular topological indexes in chemical graph theory.The M-S index and the H index of the graph G can be obtained by the independent set polynomial and the matching polynomial.In the independent polynomial and the matching polynomial of the graph G,take x=1 to get the M-S index and the H index.C1,d graph class and Z(hn)special graph classes are defined.The main work includes the following four parts.C1,d graph class and Z(hn)connected graph are defined.Independent polynomials and matching polynomials of C1,d graph class,Z(hn)special graph classes and special corona products are obtained,of which,C1,d graphs include C1,d 1,n,C1,d 2 and T1,d l.The crown product includes Pn(?)H?Cn(?)H?Sn2(?)H and Mn(?)H.The order of independent polynomials and matching polynomials of T1,d l are studied.The ordering results of the independent polynomials of T1,d l and the indices of M-S index is obtained,and the corresponding extremal graphs are characterized.Y1,4 5 is a graph with the largest M-S index in a subclass.More specifically,I(T1,3 2;x)<I(T1,4 2;x)<I(T1,3 3;x)<I(T1,4 2;x)<I(T1,3 4;x)<I(T1,4 4;x)<I(T1,3 5;x)<I(T1,4 5;x)?(T1,33)<?(T1,42)<?(T133)<?(T1,43)<?(T1,34)<?(T1,44)<?(T1,35)<?(T1,45)The counting problem of the M-S index and the H index of Cartesian product,direct product,semi strong product and strong product of path,cycle,star and complete graph are given.