The number of independent sets of unicyclic graphs with given matching number ?
The Hosoya index z(G) z ( G ) of a graph G G is defined as the number of matchings of G G and the MerrifieldSimmons index i(G) i ( G ) of G G is defined as the number of independent sets of G G . Let U(n,m) U ( n , m ) be the set of all unicyclic graphs on n n vertices with ??(G)=m ? ? ( G ) = m . Denote by U1(n,m) U 1 ( n , m ) the graph on n n vertices obtained from C3 C 3 by attaching n?2m+1 n ? 2 m + 1 pendant edges and m?2 m ? 2 paths of length 2 at one vertex of C3 C 3 . Let U2(n,m) U 2 ( n , m ) denote the n n -vertex graph obtained from C3 C 3 by attaching n?2m+1 n ? 2 m + 1 pendant edges and m?3 m ? 3 paths of length 2 at one vertex of C3 C 3 , and one pendant edge at each of the other two vertices of C3 C 3 . In this paper, we show that U1(n,m) U 1 ( n , m ) and U2(n,m) U 2 ( n , m ) have minimal, second minimal Hosoya index, and maximal, second maximal MerrifieldSimmons index among all graphs in U(n,m)?{Cn} U ( n , m ) ? { C n } , respectively.
independent set unicyclic graph matching