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

About 17 years old · traced to

Let GG be a connected graph on nn vertices, where n≥3n\ge 3. Write R(G)=∑uv∈E(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+47⌋⌊6n+27⌋−⌊n+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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.