The 2-Quasi-Regularizability Conjecture and Independence Polynomials of Wp Graphs
Hoang, Levit, Mandrescu and Pham asked for structural conditions ensuring that the independence polynomial of a $\W_p$ graph is log-concave, or at least unimodal, and conjectured that a connected $\W_2$ graph is $2$-quasi-regularizable if and only if $n(G)\ge 3α(G)$ (2026). We prove the conjecture. The key point is a local expansion theorem: if $G$ is connected and belongs to $\W_2$, then every non-maximum independent set $A$ satisfies \[ |N_G(A)|\ge 2|A|. \] Thus the only possible obstruction to $2$-quasi-regularizability in a connected $\W_2$ graph comes from maximum independent sets,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.14076
curl -X POST /api/v1/records/arxiv/2605.14076/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.14076/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'