{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-22","reactions":{}}