A k2/3k^{2/3} lower bound for the Randić index in terms of matching number

Let GG be a graph, let R(G)R(G) denote its Randić index, and let α(G)\alpha'(G) denote its matching number.

Randić-index matching conjecture. If

α(G)=k,\alpha'(G)=k,

then

R(G)ck2/3R(G)\geq ck^{2/3}

for some absolute constant c>0c>0.

The paper proves the corresponding asymptotic lower bound for graphs having a nearly-perfect matching and conjectures that the same order of growth holds for all graphs.

Sources & referencesView supporting material

Primary source

Saieed Akbari, Sina Ghasemi Nezhad, Reyhane Ghazizadeh, John Haslegrave and Elahe Tohidi, “Lower bounds for the Randić index in terms of matching number”, arXiv:2402.12884 (2024).

Additional references

2 papers in this index state this conjecture (2016–2024). The statement above is taken from the most recent of them; the others are arXiv:1607.08258.

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.