A sharp Randić bound for König--Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng
Let $α'(G)$ be the matching number of a graph $G$, and let its Randić index be $R(G)=\sum_{uv\in E(G)}(d(u)d(v))^{-1/2}$. In 2006, Aouchiche, Hansen, and Zheng conjectured that the maximum of $R(G)-α'(G)$ over all $n$-vertex graphs is attained by the complete bipartite graph whose smaller part has $\lfloor\frac{n+4}{7}\rfloor$ vertices; the conjecture has remained open since then. In this paper, we prove that every $n$-vertex König--Egerváry graph, and in particular every bipartite graph, satisfies \[ R(G)\le\sqrt{α'(G)\left(n-α'(G)\right)}, \] and we characterize the graphs attaining…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.23918
curl -X POST /api/v1/records/arxiv/2607.23918/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.23918/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'