A sharp Randić bound for König--Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng

Abstract

Let $\hat{I}{\pm }^{\prime }(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)-\hat{I}{\pm }^{\prime }(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 equality as the bipartite graphs all of whose components are semiregular with a common degree ratio. The König--Egerváry hypothesis cannot be dropped, but the Berge--Tutte formula reduces the general case to it, and in this way we determine the maximum of $R(G)-\hat{I}{\pm }^{\prime }(G)$ for every $n\ge 4$, together with all extremal graphs. The conjecture is therefore false, and it fails for infinitely many orders: the optimal part size is governed by the proportion $\frac{2-\sqrt{2}}{4}$ rather than by $\frac{1}{7}$. The two proportions give asymptotic slopes differing by less than $3.7\cdot 10^{-5}$, which is why a search over graphs of small order does not distinguish them. The equality statement fails as well, since the extremal graphs are not only the complete bipartite ones.

15 pages