PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)Vol. 69(83), pp. 41--50 (2001)
|
|
PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 69(83), pp. 41--50 (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 Prirodno-matemati\v cki fakultet, 34001 Kragujevac, p.p. 60, YugoslaviaAbstract: 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$. 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
|