The Merrifield-Simmons conjecture also holds for parity graphs

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 $σ(G)$, in vertex-deleted subgraphs. Namely, that the sign of the term $σ(G_{-u}) \cdot σ(G_{-v}) - σ(G) \cdot σ(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.

No reviews yet.

No comments yet.