On externally supported independence number of graphs
June 22, 2026
Abstract
We introduce the 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.
aUniversity of Maribor, FERI, Koroška cesta 46, 2000 Maribor, Slovenia
bUniversity of Maribor, FNM, Koroška cesta 160, 2000 Maribor, Slovenia
cIMFM, Jadranska ulica 19, 1000 Ljubljana, Slovenia
dDepartment of Mathematical Sciences, Stellenbosch University, Stellenbosch, 7600, South Africa
Keywords: externally supported independence number, isolation number, independence number, tree, computational complexity
Mathematics Subject Classification: 05C69
1 Introduction↩︎
In domination we are looking for the smallest set of vertices such that every vertex not in the set is adjacent to a vertex in the set, we say that such a set dominates the graph. Domination is often use for modeling facility location problems. For example, let a city be represented by a graph; determining where to place service facilities, so that people from every part of the city have the service in question close to their home is a facility location problem that can be solved with domination in graph theory. An optimal solution might not always be possible to implement, for example, desired locations may already be occupied by other activities, or too many services of the same kind may be too expensive, to mention just two. It is therefore often necessary to consider suitable relaxations.
One recent relaxation closely related to domination is isolation, where the chosen set is not required to dominate all the vertices of the graph. With isolation the focus falls on avoiding certain structures among the undominated vertices. Let \(\mathcal{F}\) denote the family of graphs to avoid. A set of vertices will be an \(\mathcal{F}\)-isolating set if none of the graphs in \(\mathcal{F}\) occurs as an induced subgraph of the graph that remains after removing the set and its neighbors. The minimum number \(\iota_{\mathcal{F}}(G)\) of such vertices is called the \(\mathcal{F}\)-isolation number of a graph \(G\).
In 2010 Lewis et al. [1] introduced the concept of isolation for \(\mathcal{F}=\{K_2\}\) under the name of vertex-edge domination. They characterized trees satisfying \(\iota_{\mathcal{F}}(T)=\gamma(T)\). Żyliński [2] and Ziemann proved a general upper bound on vertex-edge domination number of a graph and then later Żyliński [3] improved this result for cubic graphs. Vertex-edge domination is a special case of \(\mathcal{F}\)-isolation where \(\mathcal{F}=\{K_2\}\); in this case we refer simply to the isolation number \(\iota(G)\) of a graph. Caro and Hansberg [4] presented several lower bounds together with the general upper bound \(\iota(G)\leq\frac{n(G)}{3}\) for connected graphs. Graphs attaining this upper bound were characterized among unicyclic and block graphs by Lemańska et al. [5], and a structural description was later given by Boyer and Goddard [6]. Recently the isolation number of Cartesian products and generalized Sierpiński graphs was considered by Brešar et al. [7]. Other choices of \(\mathcal{F}\) have been studied as well, including all cycles [8], \(C_4\) [9] and \(K_k\) [10]. Variants such as total isolation [11] and independent isolation [12] have also been introduced.
To determine the isolation number \(\iota(G)\) of a graph \(G\), one seeks a set \(A\subseteq V(G)\) of minimum cardinality such that \(V(G)\) is partitioned into \(A\), the neighborhood of \(A\), and a third set that induces an independent set in \(G\). In other words, all vertices that are not dominated by \(A\) form an independent set in \(G\). While many publications on the isolation number follow domination-oriented approach, we turn the table and put independent sets into the spotlight. More precisely, we study independent sets \(B\) with the property that every vertex in \(N(B)\) has a neighbor outside the closed neighborhood \(N[B]\); we call such sets externally supported independence sets. In other words, we are interested in the independent set not dominated by an isolating set.
The paper is organized as follows. In the next section we present the notation and necessary definitions. In Section 3 we introduce externally supported independence sets and the corresponding parameter, and we study the computational complexity of the associated decision problem. In Section 4 we derive several bounds for this new parameter and compare it with the independence number. We also present an upper bound in terms of the order and the minimum and maximum degree, and we characterize all graphs that admit no nonempty externally supported independence set. In Section 5 we focus on trees and characterize extremal trees for a lower and an upper bound, and present a linear-time algorithm for externally supported independence number of a tree. The concluding section presents possible connections to other graph parameters and some ideas for further research.
2 Preliminaries↩︎
We use standard notation \([k]\) for the set \(\{1,2,\dots,k\}\), and \(K_n,\overline{K}_n,C_n,P_n\) for the complete graph, the edgeless graph, the cycle and the path, respectively, on \(n\) vertices. Throughout the paper, graphs are finite and simple.
Let \(G\) be a graph on \(n(G)\) vertices. For \(v\in V(G)\) we write \(N_G(v)\) for its open neighborhood and \(N_G[v]=N_G(v)\cup \{v\}\) for its closed neighborhood. For \(A\subseteq V(G)\) we set \(N_G[A]=\cup_{a\in A}N_G[a]\), \(N_G(A)=N_G[A]-A\). When no confusion is likely, we omit the subscript \(G\) and write \(N(v)\), \(N[v]\), \(N(A)\), and \(N[A]\). By \(G[S]\) we denote the induced subgraph of \(G\) on \(S\subseteq V(G)\), that is, the graph with vertex set \(S\) and edge set \(E(G[S])=\{uv\in E(G): u,v\in S\}\).
A set \(S\subseteq V(G)\) is an independent set of \(G\) if there are no edges in \(G\) between vertices of \(S\). Let \(A\subseteq V(G)\) and \(B=V(G)-N_G[A]\). The set \(A\) is a dominating set if \(B=\emptyset\), and it is an isolating set if \(B\) is an independent set. We say that a vertex \(v\) dominates all vertices in \(N[v]\). Clearly, every dominating set is isolating, but not every isolating set is dominating.
The maximum cardinality of an independent set of \(G\) is the independence number \(\alpha(G)\), the minimum cardinality of a dominating set of \(G\) is the domination number \(\gamma(G)\) and the minimum cardinality of an isolating set of \(G\) is the isolation number \(\iota(G)\). An independent set of cardinality \(\alpha(G)\) is called an \(\alpha (G)\)-set, a dominating set of cardinality \(\gamma(G)\) is a \(\gamma(G)\)-set, and an isolating set of cardinality \(\iota(G)\) is called \(\iota(G)\)-set.
For \(v\in V(G)\) let \({\rm deg}(v)=|N(v)|\) be the degree of \(v\). A vertex \(v\) is universal if \({\rm deg}(v)=n(G)-1\), a leaf if \({\rm deg}(v)=1\), and an isolated vertex if \({\rm deg}(v)=0\). Let \(L(G)\) be the set of all leaves of \(G\) and set \(\ell(G)=|L(G)|\). Locally, for each \(v\in V(G)\) let \(L(v)\) be the set of leaves adjacent to \(v\in V(G)\) and set \(\ell(v)=|L(v)|\). The neighbor of a leaf \(v\) is called its support vertex. Let \(S(G)\) denote the set of all support vertices of \(G\) and set \(s(G)=|S(G)|\). For \(v\in V(G)\) let \(S(v)\) be the set of all support vertices adjacent to \(v\) and set \(s(v)=|S(v)|\).
Distinct vertices \(u\) and \(v\) are twins if \(N[u]=N[v]\). Let \(u\) and \(v\) be twins. A vertex \(w\) is a support of a twin \(u\) (and \(v\)) if \(N[u]\subset N[w]\). We denote by \(TS(G)\) the set of all twin support vertices of \(G\).
3 Definition and complexity↩︎
Let \(A\) be an isolation set of \(G\). In this paper we focus on \(B=V(G)-N[A]\), the independent set left after removing \(A\) together with its closed neighborhood. This viewpoint connects isolation to the well-developed theory of independent sets and motivates studying how large such a residual independent set can be. This leads to a refined notion of independent sets tailored to isolation.
First we recall the following bound from [4]: \[\label{low95bound}
\iota(G)\geq \left\lceil\frac{n(G)+1-\alpha(G)}{\Delta(G)+1}\right\rceil.\tag{1}\] Indeed, let \(A\) be an \(\iota(G)\)-set. Then \(B=V(G)-N[A]\) is independent and, since \(A\neq\emptyset\), for any \(x\in A\) the set \(B\cup\{x\}\) is independent. Hence
\(|B|\le \alpha(G)-1\). Moreover, each vertex of \(A\) dominates at most \(\Delta(G)+1\) vertices, so \((\Delta(G)+1)|A|\ge
n(G)-|B|\). Therefore \[(\Delta(G)+1)\iota(G)\ge n(G)-(\alpha(G)-1)=n(G)+1-\alpha(G),\] which yields 1 .
Let \(A\) be an isolating set of a graph \(G\) and consider the remainder \(B=V(G)-N[A]\). By definition, \(B\) is an
independent set. However, not every independent set can occur in this way: the condition that \(B\) arises after removing \(A\) together with its closed neighborhood imposes an additional
local constraint. That is, every vertex \(v\in N(B)\) must be dominated by \(A\), and since \(A\subseteq V(G)-N[B]\), this is possible only if \(v\) has a neighbor outside \(N[B]\). This observation leads to the following notion.
A set \(B \subseteq V(G)\) is called an externally supported independence set (an ESI–set for short) if \(B\) is an independent set and every \(v\in N(B)\) has a neighbor in \(D=V(G)-N[B]\). The externally supported independence number of \(G\) (shortly the ESI–number), denoted by \(\alpha_{\rm es}(G)\), is the maximum cardinality of an ESI-set in \(G\). An ESI-set of cardinality \(\alpha_{\rm es}(G)\) will be referred to as \(\alpha_{\rm es}(G)\)-set. For convenience, we shall refer to the requirement that every vertex in \(N(B)\) has a neighbor in \(D\) as the ES-condition.
This new definition results in the following reformulation of (1 ).
Theorem 1. For any graph \(G\) we have \[\iota(G)\geq \left\lceil\frac{n(G)-\alpha_{\rm es}(G)}{\Delta(G)+1}\right\rceil.\]
Proof. Let \(A\) be an \(\iota(G)\)-set with \(A'=V(G)-N[A]\). Every vertex from \(A\) dominates at most \(\Delta(G)+1\) vertices of \(G\), and on the other hand, \(A\) needs to dominate \(n(G)-|A'|\) vertices. Clearly, \(A'\) is an ESI-set, since it is independent and each \(v\in N(A')\) has a neighbor in \(A\subseteq V(G)-N[A']\). Thus \(|A'|\le \alpha_{\rm es}(G)\), and we derive \[(\Delta(G)+1)\iota(G)\geq n(G)-|A'|\geq n(G)-\alpha_{\rm es}(G),\] which gives us the bound in the theorem. ◻
Rearranging the inequality in Theorem 1 yields the following lower bound on \(\alpha_{\rm es}(G)\).
Corollary 1. For any graph \(G\) we have \[\alpha_{\rm es}(G)\geq n(G)-\iota(G)(\Delta(G)+1).\]
To make the bound in Theorem 1 effective, one needs to be able to compute or estimate \(\alpha_{\rm es}(G)\). However, as expected, the following problem turns out to be NP-complete.
To see this, we describe the following construction of a graph \(G\) from a given graph \(H\). Let \(H\) be any graph and let \(\ell>n(H)\). We construct a new graph \(M(H,K_{\ell})\) as follows: take one copy of \(H\), one copy of the complete graph \(K_{\ell}\), and add a perfect matching between the vertices of \(H\) and an arbitrary set of \(n(H)\) vertices of \(K_{\ell}\). Clearly, the graph \(M(H,K_{\ell})\) can be constructed in polynomial time. An example of \(M(C_5,K_6)\) is shown in Figure 1. We begin with the following lemma.
Lemma 1. Let \(H\ncong K_n\) be a graph and let \(\ell>n(H)\) be an integer. If \(G=M(H,K_{\ell})\), then a set \(B\) is an \(\alpha_{\rm es}(G)\)-set if and only if it is an \(\alpha(H)\)-set.
Proof. Since \(H\ncong K_n\), we have \(\alpha(H)\geq 2\). Let \(V(H)=\{v_1,\dots,v_{n(H)}\}\), \(V(K_{\ell})=\{u_1,\dots,u_{\ell}\}\), and for each \(i\in[n(H)]\), let \(u_i\) be the vertex of \(K_{\ell}\) matched to \(v_i\) in the construction \(M(H,K_{\ell})\).
We first show that every independent set of \(H\) is an ESI-set of \(G\). Let \(A\subseteq V(H)\) be independent. If \(v_i\in N(A)\), then its matched neighbor \(u_i \notin N[A]\). Similarly, if \(u_j\in N(A)\), then \(v_j\in A\), and \(u_j\) has a neighbor \(u_{\ell}\notin N[A]\), since \(\ell>n(H)\) and \(u_{\ell}\) has no neighbors in \(H\). Therefore, \(A\) satisfies the ES-condition. In particular, every \(\alpha(H)\)-set is an ESI-set of \(G\), and hence \(\alpha_{\rm es}(G)\ge \alpha(H) \ge 2\).
Next we show that no \(\alpha_{\rm es}(G)\)-set contains a vertex of \(K_{\ell}\). Suppose for a contradiction that an \(\alpha_{\rm es}(G)\)-set \(B\) contains some \(u_j\in V(K_{\ell})\). Since \(u_j\in B\) and \(K_{\ell}\) is complete, it follows that \(V(K_{\ell})\subseteq N_G[B]\). Now let \(i\in[n(H)]\) with \(i\neq j\). If \(v_i\in B\), then \(u_i\in N(B)\), but all neighbors of \(u_i\) lie in \(N_G[B]\), so \(u_i\) has no neighbor in \(V(G)-N_G[B]\), a contradiction with the ES-condition. Hence \(v_i\notin B\) for every \(i\neq j\). Also, if \(j\leq n(H)\), then \(v_j\notin B\), since \(u_j\) is adjacent to \(v_j\) and \(B\) is independent. Therefore \(B=\{u_j\}\), contradicting \(\alpha_{\rm es}(G)\ge 2\). Thus no \(\alpha_{\rm es}(G)\)-set contains a vertex of \(K_{\ell}\), and every \(\alpha_{\rm es}(G)\)-set is contained in \(V(H)\).
It follows that every \(\alpha_{\rm es}(G)\)-set is an independent subset of \(V(H)\), and hence has size at most \(\alpha(H)\). Since every \(\alpha(H)\)-set is an ESI-set of \(G\), we already know that \(\alpha_{\rm es}(G)\ge \alpha(H)\). Therefore \(\alpha_{\rm es}(G)=\alpha(H)\), which completes the proof. ◻
We have a polynomial-time construction \(M(H,K_{\ell})\) for every non-complete graph \(H\) and \(\ell>n(H)\) such that \(\alpha_{\rm es}(G)=\alpha(H)\). The ESI Set problem belongs to NP, because for a given set \(B\) we can verify in polynomial time that \(B\) is independent and that every vertex in \(N(B)\) has a neighbor in \(V(G)\setminus N[B]\). Since the Independent Set problem is NP-complete [13], this yields the following theorem.
Theorem 2. The ESI Set problem is NP-complete.
4 Some exact results and bounds for ESI-number↩︎
We begin with some basic bounds on \(\alpha_{\rm es}(G)\). Trivially, we have \(\alpha_{\rm es}(G)\geq 0\). Since every ESI-set is independent, \(\alpha_{\rm es}(G)\) is immediately comparable to the independence number \(\alpha(G)\), and the trivial upper bound \(\alpha_{\rm es}(G)\le \alpha(G)\) holds. Note that equality occurs for edgeless graphs \(G=\overline{K}_n\) where the whole vertex set is independent and \(\alpha_{\rm es}(G)=\alpha(G)=n\) follows. Hence, throughout the remainder of this section we assume that \(G\) has at least one edge.
We continue with exact results for some well-known graph families, starting with the join \(G\vee H\) of two graphs \(G\) and \(H\). Recall that \(G\vee H\) contains disjoint copies of \(G\) and \(H\) together with all edges between \(V(G)\) and \(V(H)\).
Proposition 3. If \(G\) and \(H\) are graphs of order \(p\geq 1\) and \(r\geq 1\), respectively, then \[\alpha_{\rm es}(G\vee H)=\left\{\begin{array}{ll} \max\{\alpha_{\rm es}(G)-1,\alpha_{\rm es}(H)-1\} & ifG\cong \overline{K}_p\;\&\;H\cong \overline{K}_r, \\[0.15cm] \max\{\alpha_{\rm es}(G),\alpha_{\rm es}(H)-1\} & ifG\ncong \overline{K}_p\;\&\;H\cong \overline{K}_r, \\[0.15cm] \max\{\alpha_{\rm es}(G)-1,\alpha_{\rm es}(H)\} & ifG\cong \overline{K}_p\;\&\; H\ncong \overline{K}_r, \\[0.15cm] \max\{\alpha_{\rm es}(G),\alpha_{\rm es}(H)\} & ifG\ncong \overline{K}_p\;\&\; H\ncong \overline{K}_r. \\[0.15cm] \end{array}\right.\]
Proof. Let \(B_G\) and \(B_H\) be an \(\alpha_{\rm es}(G)\)-set and an \(\alpha_{\rm es}(H)\)-set, respectively. Whenever these sets are nonempty, choose \(g\in B_G\) and \(h\in B_H\). Since \(G\vee H\) contains all edges between \(V(G)\) and \(V(H)\), every independent set of \(G\vee H\) is contained entirely in \(V(G)\) or entirely in \(V(H)\). Thus, it is straightforward to verify that the following sets are ESI-sets of \(G\vee H\):
\(B_G-\{g\}\) and \(B_H-\{h\}\) when \(G\cong \overline{K}_p\) and \(H\cong \overline{K}_r\);
\(B_G\) and \(B_H-\{h\}\) when \(G\ncong \overline{K}_p\) and \(H\cong \overline{K}_r\);
\(B_G-\{g\}\) and \(B_H\) when \(G\cong \overline{K}_p\) and \(H\ncong \overline{K}_r\);
\(B_G\) and \(B_H\) when \(G\ncong \overline{K}_p\) and \(H\ncong \overline{K}_r\).
Hence, \(\alpha_{\rm es}(G\vee H)\geq R\), where \(R\) is the right-hand side of the claimed equality.
Assume for a contradiction that \(\alpha_{\rm es}(G\vee H)>R\geq 0\). Let \(B\neq\emptyset\) be an \(\alpha_{\rm es}(G\vee H)\)-set. As observed before, we have either \(B\subseteq V(G)\) or \(B\subseteq V(H)\). Without loss of generality, assume that \(B\subseteq V(H)\). If \(|B|>\alpha_{\rm es}(H)\), then the ES-condition fails for some vertex in \(H\) and for the same vertex the ES-condition fails also in \(G\vee H\), a contradiction. So, \(|B|\leq \alpha_{\rm es}(H)\), and the only remaining possibility is \(|B|=\alpha_{\rm es}(H)\) and \(R=\alpha_{\rm es}(H)-1\), which implies \(H\cong \overline{K}_r\). In this case \(B=V(H)\), and every vertex from \(G\) violates the ES-condition, a contradiction again. So, \(\alpha_{\rm es}(G\vee H)\leq R\) and the desired equality follows. ◻
In the proof of the next result we will use the fact that several well-known graph families can be expressed as joins. For example, complete graphs satisfy \(K_n=K_p\vee K_{n-p}\) for \(1\leq p\leq n-1\), complete bipartite graphs satisfy \(K_{p,q}=\overline{K}_p\vee \overline{K}_q\) for \(p,q\geq 1\), for wheels we have \(W_n=K_1\vee C_{n-1}\) for \(n\geq 4\), and for fans \(F_n=K_1\vee P_{n-1}\) for \(n\geq 3\).
Proposition 4. The following holds.
For every \(n\geq 3\) we have \(\alpha_{\rm es}(P_n) = \lceil\frac{n}{4}\rceil\).
For every \(n\geq 4\) we have \(\alpha_{\rm es}(C_n) = \lfloor\frac{n}{4}\rfloor\).
For every \(n\geq 2\) we have \(\alpha_{\rm es}(K_n) = 0\).
For every \(n\geq 3\) we have \(\alpha_{\rm es}(K_{1,n-1}) = n-2\).
For every \(m,n\geq 2\) we have \(\alpha_{\rm es}(K_{m,n}) = \max\{m-1,n-1 \}\).
For every \(n\geq 4\) we have \(\alpha_{\rm es}(W_n) = \lfloor\frac{n-1}{4}\rfloor\).
For every \(n\geq 4\) we have \(\alpha_{\rm es}(F_n) = \lceil\frac{n-1}{4}\rceil\).
Proof. (i) Let \(B\subseteq V(P_n)\) be an \(\alpha_{\rm es}(P_n)\)-set where \(P_n=x_1x_2\ldots x_n\). Clearly, \(\alpha_{\rm es}(P_3)=\alpha_{\rm es}(P_4)=1\). Now assume that \(n\geq 5\). We claim that the distance in \(P_n\) between any two distinct vertices of \(B\) is at least 4. Indeed, since \(B\) is independent, distance 1 is impossible. If two vertices \(x_i, x_{i+2}\in B\), then \(x_{i+1}\in N(B)\) has no neighbor in \(V(P_n)-N[B]\), contradicting the ES-condition. Similarly, if \(x_i, x_{i+3}\in B\), then \(x_{i+1},x_{i+2}\in N(B)\) have no neighbor in \(V(P_n)-N[B]\), again contradicting the ES-condition. Hence any two vertices of \(B\) are at distance at least 4 and \(\alpha_{\rm es}(P_n)\le \lceil \frac{n}{4} \rceil\). To show the opposite inequality let \(k=\lfloor \frac{n-1}{4} \rfloor\), consider the set \(B=\{x_{4i-3}\in V(P_n); \; i\in [k]\}\cup\{x_n\}\). It is straightforward to verify that \(B\) is independent and every vertex of \(N(B)\) has a neighbor outside \(N[B]\), hence \(B\) satisfies the ES-condition. Therefore, \(\alpha_{\rm es}(P_n)\geq|B|=\lceil \frac{n}{4} \rceil\).
(ii) Let \(C_n=x_1x_2\ldots x_n x_1\). The argument for the upper bound is analogous to the one for paths. In particular, if \(B\subseteq V(C_n)\) is an \(\alpha_{\rm es}(C_n)\)-set and \(x_i\in B\), then none of \(x_{i-3},x_{i-2},x_{i-1},x_{i+1},x_{i+2},x_{i+3}\) (indices taken modulo \(n\)) can belong to \(B\), since otherwise one obtains a vertex in \(N(B)\) whose both neighbors lie in \(N[B]\), contradicting the ES-condition. Hence, vertices of \(B\) are pairwise at distance at least 4, which implies \(4|B|\leq n\) and therefore \(\alpha_{\rm es}(C_n)=|B|\leq \lfloor \frac{n}{4} \rfloor\). To show the opposite inequality, let \(k=\lfloor \frac{n}{4} \rfloor\) and consider the set \(B=\{x_{4i-3}\in V(C_n); \; i\in [k]\}\). It is straightforward to verify that \(B\) is independent and every vertex of \(N(B)\) has a neighbor outside \(N[B]\), hence \(B\) satisfies the ES-condition. Therefore, \(\alpha_{\rm es}(C_n)\geq|B|=\lfloor \frac{n}{4} \rfloor\).
For (iii) observe that \(N[v]=V(K_n)\) holds for every vertex \(v\in K_n\) and no vertex can be in an ESI-set. So, ESI-set of \(K_n\) is empty and thus \(\alpha_{\rm es}(K_n)=0\). In addition, (iv), (v), (vi), (vii) follow directly from Proposition 3, and additionally by (ii) for \(W_n\), and (i) for \(F_n\). ◻
We can use (i) and (ii) of Proposition 4 to motivate the study of \(\alpha_{\rm es}(G)\). Let \(G\) be \(P_n\) or \(C_n\). Then \(\alpha(G)\) is about \(\frac{n}{2}\), whereas \(\alpha_{\rm es}(G)\) is about \(\frac{n}{4}\). Since \(\Delta(G)=2\), the bound (1 ) gives a lower bound on \(\iota(G)\) of about \(\frac{n}{6}\), whereas Theorem 1 gives a lower bound of about \(\frac{n}{4}\), which is substantially stronger.
If a graph \(G\) has at least one edge we can improve the trivial bound as follows.
Theorem 5. For any graph \(G\) with at least one edge we have \[0\leq\alpha_{\rm es}(G)\leq\alpha(G)-1.\]
Proof. The inequality \(\alpha_{\rm es}(G)\ge 0\) is trivial. To prove the upper bound, let \(uv\in E(G)\) and suppose for a contradiction that \(\alpha_{\rm es}(G)=\alpha(G)\). Let \(B\) be an \(\alpha_{\rm es}(G)\)-set. If \(u\in B\), then \(v\in N(B)\), and by the ES-condition \(v\) has a neighbor \(x\) in \(V(G)-N[B]\). Since \(x\notin N[B]\), the vertex \(x\) is not adjacent to any vertex of \(B\), and hence \(B\cup\{x\}\) is an independent set of \(G\) with more vertices than \(B\), a contradiction. The same argument applies if \(v\in B\). Thus, \(u,v\notin B\). If \(\{u,v\}\cap N(B)\neq\emptyset\), then the ES-condition yields \(x\in V(G)-N[B]\) and we argue exactly as in the previous case to get a contradiction. Therefore \(u,v\notin N[B]\). Therefore, \(u,v\notin N[B]\). In particular, \(v\) is not adjacent to any vertex of \(B\), and since also \(v\notin B\), the set \(B\cup\{v\}\) is independent of size \(|B|+1\), a final contradiction. Hence \(\alpha_{\rm es}(G)\le \alpha(G)-1\). ◻
We next characterize graphs with \(\alpha_{\rm es}(G)=0\), that is, graphs that admit no nonempty ESI-set. Our main tool is the following local criterion, which identifies vertices that cannot belong to any ESI-set.
Lemma 2. Let \(G\) be a graph and let \(x\in V(G)\). Then \(x\) does not belong to any ESI-set of \(G\) if and only if there exists \(y\in N(x)\) such that \(N[y]\subseteq N[x]\).
Proof. Assume first that \(x\) belongs to no ESI-set. In particular, the singleton \(\{x\}\) is not an ESI-set. Since \(\{x\}\) is independent, it must fail the ES-condition, and hence there exists \(y\in N(x)\) that has no neighbor in \(V(G)-N[x]\). Equivalently, \(N(y)\subseteq N[x]\), and since \(y\in N(x)\), we obtain \(N[y]\subseteq N[x]\).
Conversely, assume that there exists \(y\in N(x)\) with \(N[y]\subseteq N[x]\). Let \(B\) be any independent set with \(x\in B\). Then \(y\in N(B)\) and \(N(y)\subseteq N[y]\subseteq N[x]\subseteq N[B]\), so \(y\) has no neighbor in \(V(G)-N[B]\). Hence \(B\) fails the ES-condition and therefore cannot be an ESI-set. Since \(B\) was arbitrary, \(x\) belongs to no ESI-set. ◻
As an immediate consequence of Lemma 2, we obtain the following forbidden-vertex conditions for ESI-sets.
Corollary 2. If \(B\) is an ESI-set of a graph \(G\), then \(B\) contains neither a universal vertex, nor a support vertex, nor a twin, nor a support of a twin.
We next present two characterizations of graphs with \(\alpha_{\rm es}(G)=0\), that is, graphs admitting no ESI-set. First we give a neighborhood-inclusion condition, and then we refine it into an explicit description of the vertex types that force \(\alpha_{\rm es}(G)=0\).
Theorem 6. The following statements are equivalent for a graph \(G\):
\(\alpha_{\rm es}(G)=0\);
every vertex \(x\in V(G)\) has a neighbor \(y\in N_G(x)\) such that \(N_G[y]\subseteq N_G[x]\);
every vertex of \(G\) is a universal vertex or a twin or support of a twin.
Proof. \((i)\Rightarrow (ii)\). Assume that \(\alpha_{\rm es}(G)=0\). Since no nonempty ESI-set exists, no vertex \(x\in V(G)\) can belong to an ESI-set. By Lemma 2, this implies that for every \(x\in V(G)\) there exists a neighbor \(y\in N(x)\) such that \(N[y]\subseteq N[x]\).
\((ii)\Rightarrow (i)\). Assume that for every \(x\in V(G)\) there exists a neighbor \(y\in N(x)\) such that \(N[y]\subseteq N[x]\). By Lemma 2 \(x\) belongs to no ESI-set and therefore no nonempty ESI-set exists. So, \(\alpha_{\rm es}(G)=0\) follows.
\((i)\Rightarrow(iii)\). Assume that there exists a vertex \(v_1\in V(G)\) that is neither universal, nor a twin, nor a support of a twin. We show that then \(\alpha_{\rm es}(G)>0\).
If \(v_1\) belongs to some ESI-set, then \(\alpha_{\rm es}(G)>0\) and we are done. Otherwise, \(v_1\) belongs to no ESI-set. By Lemma 2, there exists a neighbor \(u\in N(v_1)\) such that \(N[u]\subseteq N[v_1]\). Choose such a vertex \(v_2\in N(v_1)\) with \(N[v_2]\subseteq N[v_1]\) that is minimal with respect to set inclusion among all vertices \(u\in N(v_1)\) satisfying \(N[u]\subseteq N[v_1]\).
If \(v_2\) belongs to some ESI-set, then \(\alpha_{\rm es}(G)>0\) and we are done. Otherwise, \(v_2\) belongs to no ESI-set, and Lemma 2 yields a neighbor \(v_3\in N(v_2)\) such that \(N[v_3]\subseteq N[v_2]\). By the choice of \(v_2\), this inclusion cannot be strict, and hence \(N[v_3]=N[v_2]\). Thus \(v_2\) and \(v_3\) are twins. Since \(v_1\) is not a twin, we have also \(N[v_2]\subset N[v_1]\), which means that \(v_1\) is a support of a twin, a contradiction.
Therefore, \(v_2\) must belong to some ESI-set, and consequently \(\alpha_{\rm es}(G)>0\).
\((iii)\Rightarrow (i)\). Assume \((iii)\) and suppose for a contradiction that \(\alpha_{\rm es}(G)>0\). Let \(B\) be a nonempty ESI-set and pick \(x\in B\). By \((iii)\), the vertex \(x\) is universal, or a twin, or a support of a twin, contradicting Corollary 2. Hence \(\alpha_{\rm es}(G)=0\). ◻
Recall that every dominating set is isolating, and hence \(\iota(G)\le \gamma(G)\) for every graph \(G\). It is therefore natural to ask for which graphs equality \(\gamma(G)=\iota(G)\) holds. In [14], Lemańska et al.characterize trees for which \(\gamma(G)=\iota(G)\) holds. Furthermore, in [7], Brešar et al.identify several graph families for which the equality is satisfied.
Theorem 6 describes graphs with \(\alpha_{\rm es}(G)=0\). Although this class is fairly large, the condition \(\alpha_{\rm es}(G)=0\) is not necessary for \(\gamma(G)=\iota(G)\). Indeed, for the star \(K_{1,n-1}\) we have \(\gamma(K_{1,n-1})=\iota(K_{1,n-1})=1\), while \(\alpha_{\rm es}(K_{1,n-1})=n-2>0\) for \(n>2\) by Proposition 4.
Nevertheless, \(\alpha_{\rm es}(G)=0\) is a sufficient condition for \(\gamma(G)=\iota(G)\). In fact, Theorem 6 \((ii)\) implies that every vertex \(x\) has a neighbor \(y\in N(x)\) with \(N[y]\subseteq N[x]\), which forces any isolating set to be dominating. Consequently, \(\gamma(G)=\iota(G)\). Combining this with Theorem 1 yields the following standard lower bound; see, e.g., [15].
Corollary 3. If \(G\) is a graph with \(\alpha_{\rm es}(G)=0\), then \(\gamma(G)=\iota(G)\geq \left\lceil\frac{n(G)}{\Delta(G)+1}\right\rceil\).
Now we turn our attention to graphs attaining the upper bound in Theorem 5, that is, to graphs for which \(\alpha_{\rm es}(G)=\alpha(G)-1\). Let \(B\) be an ESI-set of a graph \(G\) and let \(B'\subseteq B\). The external private neighborhood of \(B'\) with respect to \(B\), denoted by \(\mathrm{epn}(B',B)\), is defined by \[\mathrm{epn}(B',B)=N(B')- N(B-B').\] Equivalently, \(\mathrm{epn}(B',B)\) consists of all vertices that are adjacent to at least one vertex of \(B'\) and to no vertex of \(B-B'\).
Proposition 7. Let \(G\) be a graph with at least one edge. Then \(\alpha_{\rm es}(G)=\alpha(G)-1\) if and only if either \(G=K_n\) for some \(n\geq 2\), or for every \(\alpha_{\rm es}(G)\)-set \(B\) the following two conditions hold:
the set \(D=V(G)-N[B]\) induces a complete graph, and
for every subset \(B'\subseteq B\), \(\alpha(G[\mathrm{epn}(B',B)\cup D]) \leq |B'|+1\).
Proof. Let \(G\) be a graph with at least one edge. Assume first that \(\alpha_{\rm es}(G)=\alpha(G)-1\). The statement clearly holds if \(G\cong K_n\), \(n\geq 2\). Assume henceforth that \(G\) is not complete and let \(B\) be an \(\alpha_{\rm es}(G)\)-set and \(D=V(G)-N[B]\). Then \(|B|=\alpha_{\rm es}(G)=\alpha(G)-1\) and \(D\neq\emptyset\). For every \(v\in D\), the set \(B\cup\{v\}\) is independent (since \(v\notin N[B]\)) and has size \(|B|+1=\alpha(G)\), and hence it is an \(\alpha(G)\)-set. Now suppose for a contradiction that the set \(D\) does not induce a complete graph. Then there exist two nonadjacent vertices \(x,y\in D\) and \(B\cup\{x,y\}\) is an independent set. Therefore, \(\alpha(G) \ge |B|+2 =\alpha(G)+1\), a contradiction. Hence \(D\) induces a complete graph, proving condition \((i)\).
To prove condition \((ii)\), assume to the contrary there exists an \(\alpha_{\rm es}(G)\)-set \(B\) with a subset \(B'\subseteq B\) such that \(\alpha(G[\mathrm{epn}(B',B)\cup D]) > |B'|+1\). Let \(H=G[\mathrm{epn}(B',B)\cup D]\) and let \(I\) be an \(\alpha(H)\)-set. Then \(I\cup (B-B')\) is an independent set of \(G\) \[\alpha(G)\geq |I\cup (B-B')|>|B'|+1+|B|-|B'|=|B|+1=\alpha_{\rm es}(G)+1,\] contradicting the assumption that \(\alpha_{\rm es}(G)=\alpha(G)-1\).
Now assume that conditions \((i)\) and \((ii)\) hold. Let \(B\) be an \(\alpha_{\rm es}(G)\)-set and put \(D=V(G)-N[B]\). To the contrary assume that \(\alpha_{\rm es}(G)\leq \alpha(G) -2\) and let \(A\) be an \(\alpha(G)\)-set. If \(B\subseteq A\), then \(|A-B|\ge 2\) and \(A-B\subseteq D\) (since \(A\) is independent), so \(D\) contains two nonadjacent vertices, contradicting \((i)\). Therefore \(B\not\subseteq A\). Let \(A'=A-B\), \(B_1=B\cap A\) and \(B_2=B-A\). Since \(\alpha_{\rm es}(G)\leq \alpha(G) -2\), it follows that \[|B_1|+|A'|=|A|=\alpha(G)\geq \alpha_{\rm es}(G)+2=|B_1|+|B_2|+2\] and therefore \(|A'|\geq |B_2|+2\). Furthermore, since \(A\) is independent, no vertex of \(A'\) is adjacent to any vertex of \(B_1\). Consequently, every vertex of \(A'\) lies either in \(D\) or in \(N(B_2)-N(B_1) =\mathrm{epn}(B_2,B)\). That is, \(A'\subseteq \mathrm{epn}(B_2,B)\cup D\), and therefore \[\alpha\left(G[\mathrm{epn}(B_2,B)\cup D]\right)\ge |A'|\ge |B_2|+2,\] contradicting condition \((ii)\) applied to \(B'=B_2\). Therefore \(\alpha_{\rm es}(G)=\alpha(G)-1\), as required. ◻
The necessity of condition \((ii)\) is illustrated by the graph \(G\) shown in Figure 2. We have \(\alpha_{\rm es}(G)=2\), and \(B=\{5,8\}\) is the unique \(\alpha_{\rm es}(G)\)-set. Then \(D=V(G)\setminus N[B]\) induces a complete graph, so condition (i) holds. However, for \(B'=\{5\}\), \(\mathrm{epn}(B',B)=\{4,6\}\) and \[\alpha(G[\mathrm{epn}(B',B)\cup D]) \ge 3 > |B'|+1=2,\] so condition \((ii)\) fails. On the other hand, \(\alpha(G)=4\) and \(\alpha_{\rm es}(G)=2\), and hence \(\alpha_{\rm es}(G)\ne \alpha(G)-1\).
Next, we present an upper bound that depends on \(\delta(G), \Delta(G)\) and \(n(G)\). Two direct consequences follows, one for \(k\)-regular graphs where
\(\Delta(G)=\delta(G)=k\) and one for trees where \(\delta(T)=1\).
Proposition 8. For any graph \(G\), with \(\Delta(G)\geq 2\), we have \[\alpha_{\rm es}(G) \leq \frac{\Delta(G)(\Delta(G)-1)}{\Delta(G)^2+\Delta(G)(\delta(G)-1)+\delta(G)}n(G)\] and this bound is sharp.
Proof. Let \(B\) be an \(\alpha_{\rm es}(G)\)-set and let \(D=V(G)-N[B]\). Every vertex in \(B\) is adjacent to at least \(\delta(G)\) vertices in \(N(B)\), while every vertex in \(N(B)\) is adjacent to at least one vertex in \(D\) and therefore it has at most \(\Delta(G)-1\) vertices in \(B\). Furthermore, every vertex in \(D\) is adjacent to at most \(\Delta(G)\) vertices in \(N(B)\). Counting the edges between \(B\) and \(N(B)\) gives \(\delta(G)|B|\leq (\Delta(G)-1)|N(B)|\). Also, counting the edges between \(N(B)\) and \(D\), we have \(|N(B)|\leq \Delta(G)|D|\). It now follows that \[\begin{align} n(G)&= |B|+|N(B)|+|D|\\ &\geq |B| +|N(B)|(1+1/\Delta(G))\\ &\geq |B|+\left (\frac{\Delta(G)+1}{\Delta(G)}\right )\left (\frac{\delta(G)}{\Delta(G)-1}\right )|B|\\ & = \left (\frac{\Delta(G)(\Delta(G)-1)+\delta(G)(\Delta(G)+1)}{\Delta(G)(\Delta(G)-1)}\right )|B|. \end{align}\] Since \(B\) is an \(\alpha_{\rm es}(G)\)-set, rearranging the above inequality yields the desired bound.
For sharpness, let \(G=K_{m,m}\) with \(m\ge 2\). Then \(\delta(G)=\Delta(G)=m\) and \(n(G)=2m\), so the bound gives \(\alpha_{\rm es}(G)\le m-1\). Equality follows from Proposition 4. ◻
Corollary 4. For a \(k\)-regular graph \(G\) we have \[\alpha_{\rm es}(G) \leq \frac{k-1}{2k}n(G).\]
Corollary 5. For any tree \(T\ncong K_1\) we have \[\alpha_{\rm es}(T) \leq \frac{\Delta(T)(\Delta(T)-1)}{\Delta(T)^2+1}n(T).\]
With the following construction we give a class of graphs attaining the bound in Proposition 8. For \(r<s\), these graphs satisfy \(\delta(G)\ne \Delta(G)\). Take \(r\ge 1\) copies of \(K_{1,s}\), for \(s\ge 2\), and denote the center of the \(k\)-th copy by \(c_k\) and its leaves by \(b_{k,1},\dots,b_{k,s}\), where \(k\in [r]\). For each \(i\in [s]\), add \(s-1\) new vertices \(a_{i,1},\dots,a_{i,s-1}\), and join each vertex \(a_{i,j}\), where \(j\in [s-1]\), to all vertices \(b_{k,i}\) for \(k\in [r]\). Let the resulting graph be denoted by \(G(r,s)\). For \(s\ge r\), we have \(n(G(r,s))=r+rs+s(s-1)\), \(\delta(G(r,s))=r\), and \(\Delta(G(r,s))=s\). It follows from Proposition 8 that \(\alpha_{\rm es}(G(r,s))\le s(s-1)\). Let \(B=\{a_{i,j}: i\in [s], j\in [s-1]\}\). Then \(B\) is an independent set and \(V(G(r,s))- N[B]=\{c_1,\dots,c_r\}\). Since each \(b_{k,i}\) is adjacent to \(c_k\), it follows that \(B\) is an ESI-set. Hence \(\alpha_{\rm es}(G(r,s))=s(s-1)\). As a side effect, we also obtain that \(\alpha(G(r,s))\ge \alpha_{\rm es}(G(r,s))+r\), since \(B\cup\{c_1,\dots,c_r\}\) is an independent set. In particular, \(G_i=G(i,i)\) yields a family of graphs for which \(\alpha(G_i)-\alpha_{\rm es}(G_i)\ge i\), and hence the difference tends to infinity as \(i\to\infty\).
5 Trees↩︎
In this section, we establish general upper and lower bounds for the externally supported independence number of trees, and characterize the trees for which these bounds are attained.
To prove the lower bound we use the following construction of an ESI-set \(B\) for \(T\), which we call a canonical ESI-set of \(T\). For each support vertex \(w\in S(T)\) choose exactly one leaf \(t_w\in L(w)\), and define \[B=L(T)-\{t_w: w\in S(T)\}.\] Put \(D=V(T)-N[B]\). Then \(|B|=\ell(T)-s(T)\), and \(B\) is an ESI-set: indeed, \(B\) is independent, and every vertex in \(N(B)\) is a support of some leaf in \(B\), hence it has a neighbor in \(D\), namely the chosen leaf adjacent to that support. In particular, both vertices of \(K_2\) are leaves and supports, so \(\ell(K_2)-s(K_2)=0\).
Let \(B\) be a canonical ESI-set and let \(D=V(G)-N[B]\). The pair \((B,D)\) is called a canonical pair. Define an operation called a switch at \(x\in S(T)\) as moving \(x\) together with all its leaf neighbors to \(D_x\), and moving the chosen leaves \(t_w\) (for each \(w\in S(x)\)) from \(D\) to \(B_x\). That is, \[B_x=(B- L(x))\cup \{t_w:w\in S(x)\}\] and \[D_x=\bigl(D-\{t_w:w\in S(x)\}\bigr)\cup\{x\}\cup L(x).\] Then \(B_x\) is an ESI-set because \(D_x\) dominates \(N(B_x)\).
Let \(B'\) be an ESI-set and let \(D'\) be a set dominating \(N(B')\). Suppose that \(x\in S(T)\cap D'\) and \(t_x\in L(x)\). The operation called a reverse switch at \(x\) is the inverse of a switch at \(x\), see Figure 3. For each support vertex \(w\in S(x)\) choose exactly one leaf \(t_w\in L(w)\), and define
\[B^x=(B'-\{t_w:w\in S(x)\})\cup (L(x)-\{t_x\})\] and \[D^x=((D'-\{x\})-(L(x)-\{t_x\}))\cup \{t_w:w\in S(x)\}.\] Again, \(D^x\) dominates \(N(B^x)\) and thus \(B^x\) is an ESI-set.
![Figure 3: An example illustrating a switch at x and a reverse switch at x. White square vertices belong to an ESI-set X and black vertices belong to V(G)-N[X].](/article/2606.22972/_pdflatex/lcmqusjp.png "fig:")
Theorem 9. If \(T\) is a tree, then \(\alpha_{\rm es}(T)\geq \ell(T)-s(T)\), where equality holds if and only if \(V(T)=S(T)\cup L(T)\) and \(s(v) \leq \ell(v)-1\) for every \(v\in S(T)\).
Proof. Let \(T\) be a tree and let \(B\) be its canonical ESI-set. So, \(|B|=\ell(T)-s(T)\) and the lower bound \(\alpha_{\rm es}(T)\geq |B|=\ell(T)-s(T)\) follows. We next characterize when the equality holds.
We first prove that if \(V(T)-(S(T)\cup L(T))\neq \emptyset\), then \(\alpha_{\rm es}(T)>\ell(T)-s(T)\).
Let \(v\in V(T)-(S(T)\cup L(T))\) and let \(z\) be a leaf at minimum distance from \(v\) with \(v=v_0,v_1,\dots,v_k=z\) the unique \(v\)–\(z\) path. Then \(v_{k-1}\in S(T)\). Since \(v\) is not a support vertex, we have \(k\ge 2\), and hence \(u=v_{k-2}\) is a non-leaf vertex with \(\ell(u)=0\) and \(w=v_{k-1}\in S(u)\). In a canonical ESI-set \(B\), the chosen leaf \(t_w\) satisfies \(t_w\notin B\). Define \(B^\star=B\cup\{t_w\}\), which is clearly an independent set. Then we have \(|B^\star|=|B|+1\). Let \(D^\star=V(T)-N[B^\star]\). Since \(u\) is not adjacent to any leaf, it is not adjacent to any vertex of \(B^\star\), and thus \(u\in D^\star\). We now verify the ES-condition for \(B^\star\). Every vertex of \(N(B)\) keeps an external neighbor in \(D^\star\) as in the canonical construction. Moreover, the only vertex that may be newly added to \(N(B^\star)\) is \(w\), which has a neighbor in \(D^\star\), namely \(u\). Hence \(B^\star\) is an ESI-set and therefore \(\alpha_{\rm es}(T)\ge |B^\star|=|B|+1>|B|=\ell(T)-s(T)\).
Now we prove that the existence of a support vertex \(v\) with \(s(v)>\ell(v)-1\) forces the strict inequality \(\alpha_{\rm es}(T)>\ell(T)-s(T)\). Let \(v\in S(T)\) with \(s(v)>\ell(v)-1\) and perform a switch at \(v\) on the canonical pair \((B,D)\) to obtain \((B_v,D_v)\). Since \(B\cap L(v)=L(v)-\{t_v\}\), we remove \(\ell(v)-1\) leaves from \(B\) and add \(s(v)\) leaves (the vertices \(t_w\) for every \(w\in S(v)\)) to obtain \(B_v\). Therefore \(|B_v|=|B|-(\ell(v)-1)+s(v) > |B|\), since \(s(v)>\ell(v)-1\), and hence \(\alpha_{\rm es}(T)\ge |B_v|>|B|=\ell(T)-s(T)\).
Conversely, assume that \(V(T)=S(T)\cup L(T)\) and \(s(v)\le \ell(v)-1\) holds for every \(v\in S(T)\). Suppose for a contradiction that \(\alpha_{\rm es}(T)>\ell(T)-s(T)\), and let \(B\) be an \(\alpha_{\rm es}(T)\)-set with \(D=V(T)-N[B]\). Among all \(\alpha_{\rm es}(T)\)-sets choose \(B\) so that \(|S(T)\cap D|\) is minimum.
If \(S(T)\cap D\neq\emptyset\), pick \(x\in S(T)\cap D\) and perform a reverse switch at \(x\), obtaining an ESI-set \(B^{x}\). By construction, \(|B^{x}|=|B|-s(x)+(\ell(x)-1)\;\ge\;|B|\). Since \(|B|=\alpha_{\rm es}(T)\), we have \(|B^{x}|=|B|\), while the reverse switch removes \(x\) from \(D\cap S(T)\), contradicting the choice of \(B\). Hence \(S(T)\cap D=\emptyset\).
Since \(V(T)=S(T)\cup L(T)\) and \(S(T)\cap D=\emptyset\), it follows that \(D\subseteq L(T)\), i.e. every vertex of \(D\) is a leaf.
We may further assume that \(B\subseteq L(T)\). Indeed, if \(x\in B\) were a non-leaf vertex, then \(x\in S(T)\), contradicting Corollary 2, which states that an ESI-set contains no support vertex.
Now fix a support vertex \(w\in S(T)\). If \(B\) contains all leaves of \(L(w)\), then \(w\in N(B)\), and the ES-condition requires \(w\) to have a neighbor in \(D\), a contradiction.
Therefore \(|B\cap L(w)|\le \ell(w)-1\) for every \(w\in S(T)\), and hence \[|B| =\sum_{w\in S(T)}|B\cap L(w)| \le \sum_{w\in S(T)}(\ell(w)-1) =\ell(T)-s(T),\] contradicting \(|B|=\alpha_{\rm es}(T)>\ell(T)-s(T)\). ◻
Now we turn our attention to the upper bound. If \(T\ncong K_1\) is a tree, then Theorem 5 yields \(\alpha_{\rm es}(T)\le \alpha(T)-1\). In what follows we characterize trees that attain this bound. To do so we will need the following special families of trees, depicted in Figure 4.
Let \(\mathcal{A}\) be the family of trees constructed as follows. Start with a star \(K_{1,t}\), where \(t\ge 2\), with center \(x\). For each leaf \(v\) of this star, attach \(k_v\ge 1\) new leaves to \(v\).
To construct a tree \(T\) in the family \(\mathcal{B}\), start with a star \(K_{1,t}\), where \(t\ge 2\), with center \(x\). For each leaf \(v\) with the exception of precisely one leaf \(y\) of this star, attach \(k_v\ge 1\) new leaves to \(v\) (i.e., among the neighbors of \(x\), only \(y\) remains a leaf in \(T\)).
Finally, let \(\mathcal{C}\) be the family of trees constructed as follows. Start with a double star \(S_{a,b}\), where \(a,b\ge 1\), that is, the tree obtained from an edge \(xy\) by attaching \(a\) leaves to \(x\) and \(b\) leaves to \(y\). For each leaf \(v\) of \(S_{a,b}\), attach \(k_v\ge 1\) new leaves to \(v\).
We first compute the independence number of trees in \(\mathcal{A}\), \(\mathcal{B}\) and \(\mathcal{C}\). We will use the following result.
Lemma 3. [16] If \(T\) is a tree of order \(n\geq 3\), then there exists an \(\alpha(T)\)-set containing all the leaves of \(T\).
Lemma 4. Let \(T\in\mathcal{A}\cup \mathcal{B}\), and let \(x\) be the center of the initial star in the construction of \(T\). If \(B\) is the set of all vertices at distance \(2\) from \(x\), then \(\alpha(T)=|B|+1\).
Proof. Let \(T\in\mathcal{A}\cup \mathcal{B}\), and let \(x\) be the central vertex of the initial star in the construction of \(T\). By Lemma 3, there exists an \(\alpha(T)\)-set \(I\) containing all the leaves of \(T\).
If \(T\in\mathcal{B}\), the leaves of \(T\) are precisely \(y\) together with the vertices at distance \(2\) from \(x\), that is, \(L(T)=B\cup\{y\}\). Every vertex in \(V(T)-L(T)\) is a support of a leaf, hence no such vertex can belong to \(I\). Therefore \(I=L(T)\), and consequently, \(\alpha(T)=|I|=|L(T)|=|B|+1\).
Now let \(T\in\mathcal{A}\). All leaves of \(T\) are at distance \(2\) from \(x\), so \(L(T)=B\). Thus \(B\subseteq I\). Moreover, \(x\) is not adjacent to any vertex of \(B\), so \(B\cup\{x\}\) is independent and has size \(|B|+1\). Since every neighbor of \(x\) is the support of at least one leaf in \(B\), no neighbor of \(x\) can be added to an independent set containing \(B\). Hence \(B\cup\{x\}\) is maximum and \(\alpha(T)=|B|+1\). ◻
Lemma 5. If \(T\in\mathcal{C}\) and \(B\) is the set of all leaves of \(T\), then \(\alpha(T)=|B|+1\).
Proof. Let \(T\in\mathcal{C}\) and let \(xy\) be the central edge of the underlying double star \(S_{a,b}\). Let \(B=L(T)\) be the set of all leaves of \(T\). By Lemma 3, there exists an \(\alpha(T)\)-set \(I\) containing \(B\). Every vertex of \(V(T)-(B\cup\{x,y\})\) is a support vertex of a leaf from \(B\) and therefore cannot belong to \(I\). Moreover, neither \(x\) nor \(y\) is adjacent to any vertex of \(B\), so both \(B\cup\{x\}\) and \(B\cup\{y\}\) are independent. Since \(x\) and \(y\) are adjacent, no independent set containing \(B\) can contain both of them. Therefore, both \(B\cup\{x\}\) and \(B\cup\{y\}\) are maximum independent sets, and hence \(\alpha(T)=|B|+1\). ◻
Theorem 10. Let \(T\) be a nontrivial tree. Then \(\alpha_{\rm es}(T)=\alpha(T)-1\) if and only if \(T\) is a star \(K_{1,t}\), where \(t\ge 1\), or \(T\in \mathcal{A}\cup \mathcal{B} \cup \mathcal{C}\).
Proof. If \(T\) is a star \(K_{1,t}\), where \(t\ge 1\), then \(\alpha(T)=t\) and \(\alpha_{\rm es}(T)=t-1\) by Proposition 4, so \(\alpha_{\rm es}(T)=\alpha(T)-1\).
Now assume \(T\in\mathcal{A}\cup\mathcal{B}\) and let \(x\) be the center of the initial star in the construction of \(T\). If \(B\) is the set of vertices at distance \(2\) from \(x\), then \(B\) is independent. Moreover, every vertex in \(N(B)\) is adjacent to \(x\), and hence has a neighbor in \(D=V(T)-N[B]\) (indeed, \(x\in D\)). Thus \(B\) is an ESI-set. By Lemma 4, \(\alpha(T)=|B|+1\), so \(|B|=\alpha(T)-1\). Therefore \(\alpha_{\rm es}(T)\ge |B|=\alpha(T)-1\), and together with Theorem 5 we obtain \(\alpha_{\rm es}(T)=\alpha(T)-1\).
Finally, let \(T\in\mathcal{C}\) and let \(B\) be the set of all leaves of \(T\). Then \(B\) is independent. Every neighbor of a vertex in \(B\) is a support vertex adjacent to \(x\) or to \(y\), hence it has a neighbor in \(D=\{x,y\}\subseteq V(T)-N[B]\). Thus \(B\) is an ESI-set and \(\alpha_{\rm es}(T)\ge |B|\). By Lemma 5 we have \(|B|=\alpha(T)-1\), so again Theorem 5 implies \(\alpha_{\rm es}(T)=\alpha(T)-1\).
To prove the converse, assume that \(T\) is a nontrivial tree with \(\alpha_{\rm es}(T)=\alpha(T)-1\). If \(\alpha(T)=1\), then \(T= K_2\), and we are done. Hence assume \(\alpha(T)\ge 2\) and fix an \(\alpha_{\rm es}(T)\)-set \(B\). By Proposition 7, the subgraph \(W\) induced by \(D=V(T)-N[B]\) is complete. Since \(T\) is a tree, this implies \(W\in \{K_1,K_2\}\).
First we prove the claim that every component of \(T-W\) is a star whose center is the unique vertex adjacent to a vertex of \(W\). Let \(C\) be a component of \(T-W\). Because \(T\) is a tree and \(W\) is connected, \(C\) has a unique vertex \(c\in V(C)\) adjacent to precisely one vertex of \(W\). We cannot have \(C=K_1\), since \(T\) is connected and every vertex adjacent to a vertex of \(W\) must have a neighbor in \(B\). Hence there exists a vertex in \(V(C)-\{c\}\). Let \(u\in V(C)-\{c\}\) be arbitrary. Then \(u\notin W\), so \(u\in N[B]=B\cup N(B)\). If \(u\in N(B)\), then the ES-condition forces \(u\) to have a neighbor in \(W\), contradicting the fact that \(c\) is the unique vertex of \(C\) adjacent to a vertex in \(W\). Hence \(u\notin N(B)\) and therefore \(u\in B\). Since \(u\) was arbitrary, we have \(V(C)-\{c\}\subseteq B\). Since \(B\) is independent, there are no edges among vertices of \(V(C)-\{c\}\), so every edge of \(C\) is incident with \(c\). Thus \(C\) is a star centered at \(c\), as claimed. We now distinguish two possible cases.
Case 1: \(W=K_1\). Let \(V(W)=\{x\}\). Then, by the claim above, every component of \(T-W\) is a star of order at least 2 whose center is the unique neighbor of \(x\) in that component.
If \(T-W\) has exactly one component, \(T\) is a star. Otherwise every neighbor of \(x\) is the center of a star component of order at least \(2\), and hence \(T\in\mathcal{A}\).
Case 2: \(W=K_2\). Let \(W\) contain adjacent vertices \(x\) and \(y\). By the above claim, every component of \(T-W\) is a star of order at least 2 attached to exactly one of \(x\) and \(y\). If both \(x\) and \(y\) have a neighbor outside \(W\), then \(T\in\mathcal{C}\). On the other hand, if only one of \(x\) and \(y\) has a neighbor outside \(W\), then \(T\in\mathcal{B}\). ◻
Since \(K_2\) can be viewed as a star, and \(P_4 \in \mathcal{B}\), \(P_3, P_5\in \mathcal{A}\) and \(P_6\in \mathcal{C}\), Theorem 10 implies the following.
Corollary 6. For \(n\ge 2\), \(\alpha_{\rm es}(P_n)=\alpha(P_n)-1\) if and only if \(2\le n\le 6\).
Theorem 10 also shows that the highly centralized structure of a star is optimal for maximizing the externally supported independence number among trees of fixed order \(n\). In other words, if \(T\) is a tree, then \(\alpha_{\rm es}(T)\le n-2\), with equality if and only if \(T\) is a star.
6 Linear algorithm for trees↩︎
From an algorithmic point of view, observe that the ESI Set problem can be expressed in monadic second-order logic (MSO). Therefore, Courcelle’s theorem [17] implies the existence of a linear-time algorithm for graphs of bounded treewidth. Furthermore, the Courcelle–Makowsky–Rotics theorem [18] guarantees a polynomial-time algorithm for graphs of bounded clique-width. Since trees have treewidth 1, the above result already implies the existence of a linear-time algorithm for trees. In the remainder of this section, we present such an algorithm explicitly.
Let \(T\) be a rooted tree with root \(r\). For each vertex \(v\in V(T)\), denote by \(Ch(v)\) its set of children and by \(T_v\) the subtree of \(T\) rooted at \(v\). Let \(B\subseteq V(T)\) be an \(\alpha_{\rm es}(T)\)-set. Each vertex is assigned exactly one type: \(S\) if \(v\in B\), \(N\) if \(v\in N(B)\), and \(R\) if \(v\in V(T)-N[B]\). For every vertex \(v\), type \(x\in\{S,N,R\}\) and parent type \(p\in\{S,N,R\}\) we define \(DP[v][x][p]\) to be the maximum number of vertices of type \(S\) in the subtree \(T_v\), subject to \(v\) having type \(x\) and its parent having type \(p\). Impossible states take value \(-\infty\).
The algorithm processes the vertices of \(T\) in postorder, that is, after all their children have been processed. For each vertex \(v\), the values corresponding to all six possible states \(DP[v][x][p]\) are computed from the previously computed values of its children. The ESI-number of \(T\) is then obtained from the possible states of the root.
Theorem 11. If \(T\) is a rooted tree with root \(r\), then Algorithm ESI-number of a tree computes \(\alpha_{\rm es}(T)\) in \(O(n(T))\) time and \(O(n(T))\) space.
Proof. For every vertex \(v\in V(T)\), \(x\in\{S,N,R\}\) and \(p\in\{S,N,R\}\), the entry \(DP[v][x][p]\) is
defined as the maximum number of vertices of type \(S\) in the subtree \(T_v\), subject to \(v\) having type \(x\) and the
parent of \(v\) having type \(p\); impossible states take value \(-\infty\). Since the vertices are processed in postorder (that is, after all their children
have been processed), when \(v\) is processed all values \(DP[u][\cdot][\cdot]\) for children \(u\in Ch(v)\) are already computed. We next justify the three
update rules.
(A) \(v\) has type \(S\).
If \(v\) has type \(S\), then \(v\in B\) and contributes \(1\) to the objective. Moreover, since \(v\) has type \(S\) every child \(u\in Ch(v)\) must have type \(N\). Therefore, the optimal value in \(T_v\) equals \(DP[v][S][N] \;=\; 1 + \sum_{u\in Ch(v)} DP[u][N][S],\) which is exactly the update rule in case (A).
(B) \(v\) has type \(R\).
If \(v\) has type \(R\), then \(v\notin N[B]\) and the parent of \(v\) is not of type \(S\). Hence, only \(p\in\{N,R\}\) is possible. Furthermore, no child of \(v\) can be of type \(S\), so each child \(u\in Ch(v)\) may only have type \(N\) or \(R\). Since the subtrees \(T_u\) are vertex-disjoint, the optimal choice is obtained
by selecting independently, for each child \(u\), the better of the two possible states. Consequently, for \(p\in\{N,R\}\) we have \(DP[v][R][p] \;=\; \sum_{u\in
Ch(v)} \max\{DP[u][N][R],\,DP[u][R][R]\},\) which is the update rule in case (B).
(C) \(v\) has type \(N\).
If \(v\) has type \(N\), then \(v\in N(B)\) and it must be adjacent to at least one vertex of type \(S\). If \(p=S\), this requirement is already satisfied; otherwise (if \(p\neq S\)) at least one child of \(v\) must have type \(S\).
Furthermore, ES-condition imposes that if the parent of \(v\) is not of type \(R\) (if \(p\neq R\)), then at least one child of \(v\) must have type \(R\). If \(p=R\), then this condition is already satisfied. For a fixed assignment of types \(x_u\in\{S,N,R\}\) to all children \(u\in Ch(v)\) the best achievable value in \(T_u\) equals \(DP[u][x_u][N]\). Since the
subtrees \(T_u\) are disjoint, the total number of vertices of type \(S\) in \(T_v\) equals \(\sum_{u\in Ch(v)}
DP[u][x_u][N]\). Maximizing this sum over all assignments \((x_u)_{u\in Ch(v)}\) that satisfy the above two constraints yields exactly the update rule in case (C).
Since cases (A)–(C) exhaust all possibilities for the type of \(v\), it follows that, for every vertex \(v\), the computed entries \(DP[v][x][p]\) equal the
optimal number of vertices of type \(S\) in \(T_v\) under the stated boundary conditions. In particular, the optimal value for the whole tree is obtained at the root \(r\). Since the root has no parent, we evaluate it with parent type \(N\). In this way, all requirements involving the parent of the root must be satisfied within the subtree rooted at \(r\). The three possible types of the root are \(S\), \(N\), and \(R\), corresponding to the states \(DP[r][S][N]\), \(DP[r][N][N]\), and \(DP[r][R][N]\), respectively. Therefore, the returned value \(\max\{DP[r][S][N],\,DP[r][N][N],\,DP[r][R][N]\}\) is equal to \(\alpha_{\rm es}(T)\). This completes the proof of correctness.
For the time complexity, observe that we process each vertex of the tree exactly once in postorder. For every vertex \(v\), we consider only six possible states \((x,p)\), namely \((S,N)\), \((R,N)\), \((R,R)\), \((N,S)\), \((N,N)\), and \((N,R)\). In case (C), it suffices to know whether a child of type \(S\) has been selected and whether a child of type \(R\) has been selected. Therefore, only
four states need to be maintained, depending on whether neither requirement, only the requirement of having a child of type \(S\), only the requirement of having a child of type \(R\), or
both requirements have already been satisfied. When processing a child, we update a constant number of states, and therefore each child requires \(O(1)\) time. Hence, the total time spent at vertex \(v\) is \(O(|Ch(v)|)\). Since \(\sum_{v \in V(T)} |Ch(v)| = |E(T)| = n(T) - 1\), the overall running time is \(O(n(T))\). The
table \(DP\) stores \(O(1)\) values per vertex, therefore the space usage is \(O(n(T))\). ◻
7 Conclusion↩︎
In this work we initiated the study of \(\alpha_{\rm es}(G)\), which improves the lower bound for \(\iota(G)\) as presented in Theorem 1 . We showed that the ESI set problem is NP-complete for general graphs and presented a polynomial-time algorithm for \(\alpha_{\rm es}(T)\) for every tree \(T\). It would be interesting to better understand the boundary between graph classes for which \(\alpha_{\rm es}(G)\) can be computed in polynomial time and those for which the problem is NP-complete.
Problem 12. Identify graph classes where it is NP-hard to derive \(\alpha_{\rm es}(G)\) or where there exists a polynomial algorithm to determine \(\alpha_{\rm es}(G)\).
Several additional connections of \(\alpha_{\rm es}(G)\) with other graph parameters can be expected. We mention two such connections. Let \(G\) be a graph and \(f:V(G)\rightarrow \{0,1,2\}\) a map. If every vertex \(v\in V(G)\) with \(f(v)=0\) has a neighbor \(u\) with \(f(u)=2\), then \(f\) is a Roman domination function of \(G\). The Roman domination number \(\gamma_R(G)\) of \(G\) is the minimum weight \(w(f)=\sum_{v\in V(G)}f(v)\) over all Roman domination functions \(f\) of \(G\), see [19]. Now, if \(B\) is an ESI-set of \(G\) together with a dominating set \(D\) of \(N(B)\), then we can define a function \[f(v)=\left\{\begin{array}{ll} 0 & ifv\in N(B), \\[0.15cm] 1 & ifv\in B, \\[0.15cm] 2 & ifv\in D, \end{array}\right.\] which is clearly a Roman dominating function as every vertex from \(N(B)\) is dominated by \(D\). (Notice also that we can exchange \(B\) and \(D\) in the above function and we still obtain a Roman dominating function as every vertex from \(N(B)\) must have a neighbor in \(B\) as well.) Moreover, this Roman dominating function has additional properties that vertices of weight one form an independent set and there are no edges between vertices of weight one and weight two. This may be closer to independent Roman domination where in addition there are also no edges between vertices of weight two, see the seminal work [20]. Nevertheless, it seems an interesting approach for possible connections between graphs where \(\alpha_{\rm es}(G)\)-set yields an optimal (independent) Roman dominating function.
Problem 13. Describe all graphs where an \(\alpha_{\rm es}(G)\)-set yields an optimal (independent) Roman dominating function.
The other parameter is a packing, more precisely, a \(3\)-packing of a graph \(G\). Recall that a set \(P\subseteq V(G)\) forms a \(k\)-packing of \(G\) if the distance between any two vertices of \(P\) is more than \(k\) and \(k\)-packing number \(\rho_k\) of \(G\) is the maximum cardinality of a \(k\)-packing of \(G\), see [21] and the references therein. Clearly, \(\rho_1(G)=\alpha(G)\), but here we are more interested in \(\rho_3(G)\). Let \(P\) be a \(3\)-packing of \(G\). Notice first that if \(v\in P\) is a support of a leaf \(u\), then \(P'=(P\cup\{u\})-\{v\}\) is a \(3\)-packing as well and we may choose a \(3\)-packing \(P\) without any supports. Further, if \(u,v\in P\) are at distance four, then the neighbors of \(u\) and \(v\) that belong to a shortest \(u,v\)-path have a neighbor on this path outside of \(N[P]\). So, a \(3\)-packing \(P\) is an ESI-set if for every \(v\in P\) and every \(u\in N(v)\) we have \(N(u)-N[v]\neq \emptyset\). Whence the following problem.
Problem 14. Describe all graphs where \(\alpha_{\rm es}(G)=\rho_3(G)\).
Let us conclude with the following generalization obtained from \(\iota_{\mathcal{F}}(G)\) where \(\mathcal{F}\neq\{K_2\}\). In our case of \(\alpha_{\rm es}(G)\) we described the maximum cardinality of an independent set \(B\) of vertices such that \(V(G)-N[B]\) dominates \(N(B)\). To obtain a generalization, we need to consider a set of vertices \(B_{\mathcal{F}}\) such that no graph from \(\mathcal{F}\) is contained in an induced subgraph of \(G\) on vertices from \(B_{\mathcal{F}}\) and that every vertex from \(N[B_{\mathcal{F}}]-B_{\mathcal{F}}\) is dominated by \(V(G)-N[B_{\mathcal{F}}]\). Such an approach yields an upper bound for \(\iota_{\mathcal{F}}(G)\) similar to the one for \(\iota(G)\) in Theorem 1.
This work has been supported by the European Commission’s Horizon Europe Research and Innovation programme through the Marie Skłodowska-Curie Actions Staff Exchanges (MSCA-SE) under Grant Agreement no.101182819 (COVER: (C)ombinatorial (O)ptimization for
(V)ersatile Applications to (E)merging u(R)ban Problems). I.P. was partially supported by the Slovenian Research and Innovation Agency (ARIS), program no. P1–0297. A. T. was partially supported by the Slovenian Research and Innovation Agency (ARIS),
program no. P1–0297 and project no. J1–70016. D.B. was partially supported by the Slovenian Research and Innovation Agency (ARIS), program no. P2–0065 and project no. J1–70016.
We would also like to thank M. Milanič for his helpful comments and suggestions regarding the algorithmic aspects of the paper.
Authors have no conflict of interest to declare.