Id: arxiv/2606.22972 Url: https://arxiv.org/abs/2606.22972 Tags: math.CO Score: 0 Title: On externally supported independence number of graphs Domain: math.CO Source: arxiv Authors: Dragana Božović, Iztok Peterin, Adriana Roux, Aleksandra Tepeh Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-22 Page: https://delphi.science/r/arxiv/2606.22972 We introduce the \emph{externally supported independence number} $α_{\rm es}(G)$ of a graph $G$ as the maximum cardinality of an independent set $B$ with an additional condition, that vertices from $N(B)$ are dominated by vertices in $V(G)-N[B]$. This parameter yields an improved upper bound on the isolation number $ι(G)$. We show that computing $α_{\rm es}(G)$ is NP-hard, while for trees we present a linear-time algorithm. We also establish several sharp bounds on $α_{\rm es}(G)$ for general graphs, with additional refined results for trees. In several cases, we completely describe the…