Independence Polynomials of Bipartite Graphs

Given a connected graph G with vertex set VG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_G$$\end{document}, a subset I of VG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_G$$\end{document} is called independent if there are no edges between any two vertices from I. Let ik(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_k(G)$$\end{document} be the number of independent sets with cardinality k of G and let i0(G)=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_0(G)=1$$\end{document}. The independence polynomial of G is defined as I(G;x)=∑k⩾0ik(G)xk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I(G;x)=\sum _{k\geqslant 0} i_k(G)x^k$$\end{document}, where i(G)=I(G;1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i(G)=I(G;1)$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_k(G)\ (k\geqslant 2)$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i_k(G)\ (k\geqslant 2)$$\end{document} 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.