Independence Polynomials of Bipartite Graphs

Given a connected graph Gwith vertex set VG, a subset Iof VGis called independent if there are no edges between any two vertices from I. Let ik(G)be the number of independent sets with cardinality kof Gand let i0(G)=1. The independence polynomial of Gis defined as I(G;x)=∑k⩾0ik(G)xk, where i(G)=I(G;1)is called the Merrifield–Simmons index of G. In this paper, some extremal problems on the coefficients of the independence polynomial of bipartite graphs are considered. Firstly, the second largest ik(G)(k⩾2)among all bipartite graphs is determined, and the graph which simultaneously minimizes all coefficients of I(G; x) among all bipartite graphs is characterized. Secondly, the largest ik(G)(k⩾2)among all bipartite graphs with at least one cycle is determined, and the unique graph which minimizes all coefficients of I(G; x) among all bipartite graphs with given matching number (resp. diameter at most four, connectivity) is characterized as well.