Geodesic
More Examples and Counterexamples for a Conjecture of Merrifield and Simmons
Publications de l'Institut Mathématique, _N_S_69 (2001) no. 83, p. 41

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 : 05C70 05C12 
@article{PIM_2001_N_S_69_83_a6,
     author = {Yong Wang and Xueliang Li and Ivan Gutman},
     title = {More {Examples} and {Counterexamples} for a {Conjecture} of {Merrifield} and {Simmons}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {41 },
     publisher = {mathdoc},
     volume = {_N_S_69},
     number = {83},
     year = {2001},
     zbl = {0997.05069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PIM_2001_N_S_69_83_a6/}
}
TY  - JOUR
AU  - Yong Wang
AU  - Xueliang Li
AU  - Ivan Gutman
TI  - More Examples and Counterexamples for a Conjecture of Merrifield and Simmons
JO  - Publications de l'Institut Mathématique
PY  - 2001
SP  - 41 
VL  - _N_S_69
IS  - 83
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PIM_2001_N_S_69_83_a6/
LA  - en
ID  - PIM_2001_N_S_69_83_a6
ER  - 
%0 Journal Article
%A Yong Wang
%A Xueliang Li
%A Ivan Gutman
%T More Examples and Counterexamples for a Conjecture of Merrifield and Simmons
%J Publications de l'Institut Mathématique
%D 2001
%P 41 
%V _N_S_69
%N 83
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PIM_2001_N_S_69_83_a6/
%G en
%F PIM_2001_N_S_69_83_a6
Yong Wang; Xueliang Li; Ivan Gutman. More Examples and Counterexamples for a Conjecture of Merrifield and Simmons. Publications de l'Institut Mathématique, _N_S_69 (2001) no. 83, p. 41 . http://geodesic.mathdoc.fr/item/PIM_2001_N_S_69_83_a6/