pith. sign in

arxiv: 1006.4253 · v2 · pith:XVCH4M7Vnew · submitted 2010-06-22 · 🧮 math.CO

The Merrifield-Simmons conjecture holds for bipartite graphs

classification 🧮 math.CO
keywords sigmaconjecturebipartitecdotgraphsholdsmerrifield-simmonsterm
0
0 comments X
read the original abstract

Let $G = (V, E)$ be a graph and $\sigma(G)$ the number of independent (vertex) sets in $G$. Then the Merrifield-Simmons conjecture states 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 the vertices $u, v \in V$ in $G$. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.