Abstract:We introduce the \emph{externally supported independence number} $\alpha_{\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 $\iota(G)$. We show that computing $\alpha_{\rm es}(G)$ is NP-hard, while for trees we present a linear-time algorithm. We also establish several sharp bounds on $\alpha_{\rm es}(G)$ for general graphs, with additional refined results for trees. In several cases, we completely describe the extreme graph classes attaining these bounds.
From: Iztok Peterin [view email]
[v1]
Mon, 22 Jun 2026 07:52:43 UTC (25 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。