The Merrifield-Simmons conjecture holds for bipartite graphs

Abstract

Let $G=(V,E)$ be a graph and $\sigma (G)$ the number of independent (vertex) sets in $G$. Then the Merrifield-Simmons conjecture states that the sign of the term $\sigma (G_{-u})\cdot \sigma (G_{-v})-\sigma (G)\cdot \sigma (G_{-u-v})$ only depends on the parity of the distance of the vertices $u,v\in V$ in $G$. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.

arXiv comment8 pages