← All problems

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

10 years old · traced to

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.

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.

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).

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.