Lower bounds for the Randić index in terms of matching number
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916362337648640 |
|---|---|
| author | Akbari, Saieed Nezhad, Sina Ghasemi Ghazizadeh, Reyhane Haslegrave, John Tohidi, Elahe |
| author_facet | Akbari, Saieed Nezhad, Sina Ghasemi Ghazizadeh, Reyhane Haslegrave, John Tohidi, Elahe |
| contents | We investigate how small the Randić index of a graph can be in terms of its matching number, and prove several results. We give best-possible linear bounds for graphs of small excess and for subcubic graphs; in the former case the size of excess we permit is qualitatively the best possible. We show that a linear bound holds for any sparse hereditary graph class (such as planar graphs). In general, however, we show that it can be much smaller than linear. We determine the asymptotic growth rate of the minimum Randić index for graphs with a near perfect matching, and conjecture that the same bounds hold for all graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12884 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower bounds for the Randić index in terms of matching number Akbari, Saieed Nezhad, Sina Ghasemi Ghazizadeh, Reyhane Haslegrave, John Tohidi, Elahe Combinatorics 05C09 (Primary) 05C70, 05C35 (Secondary) We investigate how small the Randić index of a graph can be in terms of its matching number, and prove several results. We give best-possible linear bounds for graphs of small excess and for subcubic graphs; in the former case the size of excess we permit is qualitatively the best possible. We show that a linear bound holds for any sparse hereditary graph class (such as planar graphs). In general, however, we show that it can be much smaller than linear. We determine the asymptotic growth rate of the minimum Randić index for graphs with a near perfect matching, and conjecture that the same bounds hold for all graphs. |
| title | Lower bounds for the Randić index in terms of matching number |
| topic | Combinatorics 05C09 (Primary) 05C70, 05C35 (Secondary) |
| url | https://arxiv.org/abs/2402.12884 |