PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 69(83), pp. 4150 (2001) 

MORE EXAMPLES AND COUNTEREXAMPLES FOR A CONJECTURE OF MERRIFIELD AND SIMMONSYong Wang, Xuelian Li and Ivan GutmanDepartment of Applied Mathematics, Northwestern Polytechnical University, X'ian, Shaanxi 710072, P.R. China and Prirodnomatemati\v cki fakultet, 34001 Kragujevac, p.p. 60, YugoslaviaAbstract: Let $\sigma(G)$ be the number of independentvertex sets of a graph $G$. Merrifield and Simmons conjectured that for any connected graph $G$ and any pair of its nonadjacent vertices $u$ and $v$, $\Delta_{uv}(G) := \sigma(Gu)\,\sigma(Gv)  \sigma(G)\,\sigma(Guv)$ 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 nonbipartite connected unicyclic graphs, but not for all connected unicyclic graphs. Moreover, we find a graph $G$ for which $\Delta_{uv}(G)=0$. Classification (MSC2000): 05C70; 05C12 Full text of the article:
Electronic fulltext finalized on: 5 Feb 2002. This page was last modified: 5 Feb 2002.
© 2002 Mathematical Institute of the Serbian Academy of Science and Arts
