Aouchiche–Hansen–Zheng conjecture on the Randić index and matching number

From papers

Let GG be a connected graph on nn vertices, where n3n\ge 3. Write R(G)=uvE(G)(d(u)d(v))1/2R(G)=\sum_{uv\in E(G)}(d(u)d(v))^{-1/2} for its Randić index and let α(G)\alpha'(G) denote its matching number. Define

p=n+47,q=6n+27.p=\left\lfloor\frac{n+4}{7}\right\rfloor,\qquad q=\left\lfloor\frac{6n+2}{7}\right\rfloor.

Aouchiche–Hansen–Zheng conjecture. One has

R(G)α(G)n+476n+27n+47,R(G)-\alpha'(G)\le\sqrt{\left\lfloor\frac{n+4}{7}\right\rfloor\left\lfloor\frac{6n+2}{7}\right\rfloor}-\left\lfloor\frac{n+4}{7}\right\rfloor,

with equality if and only if G=Kp,qG=K_{p,q}.

The conjecture proposes the extremal connected graph for the difference between the Randić index and matching number. It was disproved by the existence of a counterexample; the corresponding restricted extremal problem for subcubic graphs was solved by Du, Hu, and collaborators.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pei Liu, Feiyu Nan, Suil O and Ruiling Zheng, “A sharp Randić bound for König–Egerváry graphs and a conjecture of Aouchiche, Hansen, and Zheng”, arXiv:2607.23918 (2026).

Additional references

4 papers in this index state this conjecture (2009–2026). The statement above is taken from the most recent of them; the others are arXiv:1607.08258, arXiv:1104.0426, arXiv:0906.5230.

Solutions 0

No solutions have been posted yet.