The Merrifield-Simmons conjecture also holds for parity graphs

Abstract

The Merrifield-Simmons conjectures states a relation between the distance of vertices in a simple graph $G$ and the number of independent sets, denoted as $\sigma (G)$, in vertex-deleted subgraphs. Namely, 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 $u$ and $v$ in $G$. We prove this statement in the case of parity graphs and give some evidence that this result may not be further generalized to other classes of graphs.

8 pages, 1 figure