RUC. Repositorio da Universidade da Coruña
Publicación
Artículo científico (JournalArticle)
Upper Bounds on the k-Isolation Number
[Abstract]: The isolation number of a graph G (also called the vertex-edge domination number of G), denoted by ι(G), is the size of a smallest subset D of the vertex set V(G) of G such that G −N[D] (the graph obtained by deleting the closed neighbourhood N[D] of D from G) has no edges. For k ≥ 1, the k-isolation number of G, denoted by ιk(G), is the size of a smallest subset D of V(G) such that the maximum degree of G − N[D] is at most k −1. Thus, ι1(G) = ι(G). Let n and ℓ be the number of vertices and the number of leaves of G, respectively. We show that if n ≥ 3 and G is connected and not a star, then ιk(G) ≤ n−ℓ 2 . We also show that if G is a tree T, then ι(T) ≤ n+ℓ 4 and ιk(T) ≤ n+ℓ 2k+1 for k ≥ 2. These bounds together improve the inequality ιk(T) ≤ n k+2 of Caro and Hansberg except that their inequality is better if k ≥ 2 and k−1 k+2n <ℓ< k k+2n. Each of the new bounds is attainable if it is an integer. For each of them, we characterize the graphs that attain it., The authors are grateful to the anonymous referees for checking the paper and providing constructive remarks that led to an improvement in the presentation. M. Mora is partially supported by grants Gen.Cat.DGR 2021-SGR-00266 from AGAUR and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. M.J. Souto-Salorio is partially supported by grant LATCHING (PID2023-147129OB-C21) funded by MICIU/AEI/10.13039/501100011033 and ERDF, EU, and by grant SCANNER-UDC (PID2020-113230RB-C21) funded by MICIU/AEI/10.13039/501100011033., Agència de Gestió d'Ajuts Universitaris i de Recerca; 2021-SGR-00266
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2023-150725NB-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2023-147129OB-C21
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2020-113230RB-C21