## Samenvatting

For k≥1, the k-independence number α_{k} of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α_{1}) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for α_{k}, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials.

Originele taal-2 | Engels |
---|---|

Pagina's (van-tot) | 96-109 |

Aantal pagina's | 14 |

Tijdschrift | Discrete Applied Mathematics |

Volume | 333 |

DOI's | |

Status | Gepubliceerd - 15 jul. 2023 |

### Bibliografische nota

Funding Information:The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N . The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00 .