More Examples and Counterexamples for a Conjecture of Merrifield and Simmons


Yong Wang, Xuelian Li, Ivan Gutman


Let $\sigma(G)$ be the number of independent-vertex sets of a graph $G$. Merrifield and Simmons conjectured that for any connected graph $G$ and any pair of its non-adjacent vertices $u$ and $v$, $\Delta_{uv}(G) := \sigma(G-u)\,\sigma(G-v) - \sigma(G)\,\sigma(G-u-v)$ is positive if the distance between $u$ and $v$ is odd, and negative otherwise. In earlier works by the authors the conjecture was shown to be true for trees, cycles and several other types of graphs, but a few counterexamples were discovered among dense graphs. We now prove that the conjecture is true for all bipartite and some non-bipartite connected unicyclic graphs, but not for all connected unicyclic graphs. Moreover, we find a graph $G$ for which $\Delta_{uv}(G)=0$.