betaFeedback

WorksComputer Science

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

Abstract

A vertex is uni-dominated by a set S⊆V(G)S \subseteq V(G) if exactly one vertex of SS lies in its closed neighborhood, and the uni-domination number ud∗(G)\mathrm{ud}^*(G) is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with ud∗(G)=n\mathrm{ud}^*(G) = n. Hedetniemi and Rall asked for the largest constant cc with ud∗(T)≥c⋅n\mathrm{ud}^*(T) \geq c \cdot n for every tree TT of order nn. We answer their question: the constant is 4/54/5, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study ud∗\mathrm{ud}^* under each of the two requirements separately, giving the Full-Cover variant ud0∗\mathrm{ud}^*_0 and the Non-Overlapping variant ud+∗\mathrm{ud}^*_+. The two behave very differently: on arbitrarily large graphs ud0∗\mathrm{ud}^*_0 may remain bounded by a constant, whereas ud+∗\mathrm{ud}^*_+ always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds ⌈nc⌉\lceil \sqrt[c]{n} \rceil and 4n4\sqrt{n}, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

Introduction

All graphs here are finite, simple and undirected. For a vertex vv of G=(V,E)G=(V,E), N(v)N(v) is its open neighborhood and N[v]=N(v)∪{v}N[v]=N(v)\cup\{v\} its closed neighborhood; vv is dominated by S⊆VS\subseteq V if ∣N[v]∩S∣≥1|N[v]\cap S|\ge1, and SS is a dominating set if it dominates every vertex [9, 10, 14]. Requiring every vertex to be dominated exactly once is much stronger: such a set is an efficient dominating set [1], or perfect code [2], and the closed neighborhoods of its vertices partition VV. A graph admitting such a set is called efficient. Such sets need not exist (C5C_{5} admits none), and recognizing the graphs that admit one is NP-complete [1, 13].

A closely related notion is that of a private neighbor [3, 4]: for U⊆VU\subseteq V, a vertex ww is an external private neighbor with respect to UU if w∉Uw\notin U and ww has exactly one neighbor in UU, and a self private neighbor if w∈Uw \in U and N(w)∩U=∅N(w) \cap U = \emptyset. Hedetniemi and Rall [11] shifted the objective from the sets UU to the private neighbors they produce, defining seven maximization parameters based on different types of private neighbors. One of them, ESPN(G)(G), maximizes the total number of external and self private neighbors over all U⊆VU \subseteq V, as ww is of one of these two types if and only if ∣N[w]∩U∣=1\lvert N[w] \cap U\rvert= 1, it is the maximum number of vertices a single set can dominate exactly once. They study it structurally and leave its complexity open.

We study this quantity as an optimization problem, under the domination-oriented name of uni-domination. A vertex vv is uni-dominated by S⊆VS \subseteq V if ∣N[v]∩S∣=1\lvert N[v] \cap S\rvert= 1, we write UD(S)={v:∣N[v]∩S∣=1}UD(S) = \{v : \lvert N[v] \cap S\rvert= 1\}, ud⁡(S)=∣UD(S)∣\operatorname{ud}(S) = \lvert UD(S)\rvert, and ud⁡∗(G)=max⁡{ud⁡(S):S⊆V}\operatorname{ud}^{*}(G) = \max\{\operatorname{ud}(S) : S \subseteq V\}, the uni-domination number of GG.

Thus ud⁡∗(G)=ESPN⁡(G)\operatorname{ud}^{*}(G) = \operatorname{ESPN}(G), and GG is efficient if and only if ud⁡∗(G)=∣V∣\operatorname{ud}^{*}(G) = \lvert V\rvert. A set realizing ud⁡∗(G)\operatorname{ud}^{*}(G) may leave vertices undominated and may dominate others more than once, and the two defects are not equally acceptable in applications: for facilities serving a whole network, leaving a vertex uncovered is forbidden while serving one twice only wastes resources, for transmitters whose signals interfere as soon as two of them reach a common vertex, overlaps are forbidden while an uncovered vertex is merely not served. Accordingly we write V0(S)V_0(S), UD(S)UD(S) and V+(S)V_+(S) for the sets of vertices uu with ∣N[u]∩S∣\lvert N[u] \cap S\rvert equal to 0, equal to 1 and greater than 1, the undominated, uni-dominated and over-dominated vertices, respectively. Forbidding one defect while maximizing the number of uni-dominated vertices gives the two parameters studied here: the Full-Cover variant, requiring SS to be a dominating set, and the Non-Overlapping variant, requiring the closed neighborhoods of the vertices of SS to be pairwise disjoint, respectively,

ud⁡0∗(G)=max⁡S⊆V{ud⁡(S):V0(S)=∅},ud⁡+∗(G)=max⁡S⊆V{ud⁡(S):V+(S)=∅}.\operatorname{ud}^{*}_{0}(G) = \max_{S \subseteq V}\{\operatorname{ud}(S) : V_0(S) = \emptyset\}, \qquad\operatorname{ud}^{*}_{+}(G) = \max_{S \subseteq V}\{\operatorname{ud}(S) : V_+(S) = \emptyset\}.

Each relaxes efficient domination in one direction: GG of order nn is efficient if and only if ud⁡0∗(G)=n\operatorname{ud}^{*}_{0}(G) = n, if and only if ud⁡+∗(G)=n\operatorname{ud}^{*}_{+}(G) = n, and both are bounded above by the unrestricted parameter, max⁡{ud⁡0∗(G),ud⁡+∗(G)}≤ud⁡∗(G)\max\{\operatorname{ud}^{*}_{0}(G), \operatorname{ud}^{*}_{+}(G)\} \leq\operatorname{ud}^{*}(G). Their behaviors turn out to be of a different nature. The second one places our study inside an existing line of work: it is the efficient domination number of Bange, Barkauskas and Slater [1], as recalled below, and our contribution to it is the hardness result of § 3 together with the comparison with ud⁡0∗\operatorname{ud}^{*}_{0} of § 3.3.

Preliminaries

Throughout, G=(V,E)G = (V, E) is a finite simple undirected graph of order n=∣V∣n = \lvert V\rvert, deg⁡(u)=∣N(u)∣\deg(u) = \lvert N(u)\rvert for any vertex u∈Vu \in V, and Δ\Delta is the maximum degree of the vertices of GG. For X⊆VX \subseteq V, the subgraph induced by XX, denoted G[X]G[X], has vertex set XX and contains exactly the edges of GG with both ends in XX. We write G−X=G[V∖X]G - X = G[V \setminus X] and N[X]=⋃v∈XN[v]N[X] = \bigcup_{v \in X} N[v]. A vertex adjacent to all others is universal, a vertex v≠uv \ne u with uv∉Euv \notin E is a non-neighbor of uu, and S⊆VS \subseteq V is a 22-packing [9, 12] if its vertices are pairwise at distance at least 3, equivalently if their closed neighborhoods are pairwise disjoint.

A dominating set is minimal if none of its proper subsets is dominating. Following Cockayne, Hedetniemi and Miller [4], a set SS is irredundant if every v∈Sv \in S has a private neighbor with respect to SS, that is, a vertex ww with N[w]∩S={v}N[w]\cap S = \{v\}, which is an external private neighbor if w≠vw \ne v and a self private neighbor if w=vw = v. A dominating set is minimal if and only if it is irredundant [4, 9]. Indeed, as every superset of a dominating set is dominating, a dominating set SS is minimal if and only if, for every v∈Sv \in S, the set S∖{v}S \setminus\{v\} leaves some vertex ww undominated. As ww is dominated by SS, this means exactly that N[w]∩S={v}N[w] \cap S = \{v\}, that is, ww is a private neighbor of vv. For all other standard notions we follow [9, 10].

Both of our reductions start from the following NP-complete problem [6].

Restricted Exact Cover by 3-Sets (RX3C)

Instance: A finite set XX with ∣X∣=3p|X| = 3p and a collection C\mathcal{C} of 3-element subsets of XX in which every element of XX occurs in exactly three subsets. Question: Is there a subcollection C∗⊆C\mathcal{C}^{*} \subseteq\mathcal{C} that contains every element of XX exactly once?

Related Work

Closest to this paper is a line of research measuring how far a graph is from being efficient. Bange, Barkauskas and Slater introduced the efficient domination number F(G)F(G), the maximum number of vertices that can be dominated by a set dominating no vertex more than once, so that GG is efficient if and only if F(G)=nF(G) = n [1, 15]. In our notation ud+∗(G)=F(G)\mathrm{ud}^{*}_{+}(G) = F(G), we keep the notation ud+∗\mathrm{ud}^{*}_{+} since our aim is to compare the two constrained variants of ud∗\mathrm{ud}^{*} within one framework. Grinstead and Slater defined the influence I(S)=∑v∈S(1+deg⁡(v))I(S) = \sum_{v\in S}(1 + \deg(v)) of a set SS and observed that a set dominates no vertex more than once precisely when it is a 22-packing, whence ud+∗(G)=max⁡{I(S):S a 2-packing}\mathrm{ud}^{*}_{+}(G) = \max\{I(S) : S\text{ a 2-packing}\} [7, 15]. Goddard, Oellermann, Slater and Swart [5] proved the sharp bounds ud+∗(G)≥1+n−1\mathrm{ud}^{*}_{+}(G) \ge1 + \sqrt{n - 1} for every graph and ud+∗(T)≥8(n+2)−4\mathrm{ud}^{*}_{+}(T) \ge\sqrt{8(n + 2)} - 4 for every tree, and deciding whether ud+∗(G)≥k\mathrm{ud}^{*}_{+}(G) \ge k for an input kk is NP-complete [1, 5], whereas ud+∗(T)\mathrm{ud}^{*}_{+}(T) is computable in polynomial time on trees [1]. The companion of ud+∗\mathrm{ud}^{*}_{+} on the domination side is the redundance R(G)=min⁡{I(S):S dominating}R(G) = \min\{I(S) : S\text{ dominating}\} [7], which differs from ud0∗\mathrm{ud}^{*}_{0}: since I(S)=∑u∈V∣N[u]∩S∣I(S) = \sum_{u\in V}|N[u] \cap S|, the quantity R(G)R(G) minimizes the total excess of domination, whereas ud0∗\mathrm{ud}^{*}_{0} maximizes the number of vertices whose excess is zero, and an excess of a given total size may be concentrated on one vertex or spread over many. Excess domination in this sense was studied in [8], and efficient versions of multiple domination in [15].

Hedetniemi and Rall [11] initiated the study of seven private neighbor parameters, determining ud∗/ESPN\mathrm{ud}^{*}/\mathrm{ESPN} for paths, cycles and complete bipartite graphs. They also observed that ud∗(T)≥n/2\mathrm{ud}^{*}(T) \ge n/2 for every tree and exhibited a family attaining 4n/54n/5, which led them to ask for the largest constant cc such that ud∗(T)≥c⋅n\mathrm{ud}^{*}(T) \ge c \cdot n holds for every tree. We settle this question.

Our Results

Our main result is that every tree TT of order nn satisfies ud⁡0∗(T)≥4n/5\operatorname{ud}^{*}_{0}(T) \ge4n/5 and that a dominating set attaining this bound can be computed in linear time (Theorem 3, Corollaries 4 and 5). Moreover, as shown in [11], the constant 4/54/5 cannot be improved, so that our result answers Problem 1 of [11]. On general graphs the same variant behaves very differently: we prove constructively that ud⁡0∗(G)≥2\operatorname{ud}^{*}_{0}(G) \ge2 for every graph of order n≥2n \ge2 (Theorem 1), and we exhibit, for every constant c≥2c \ge2, arbitrarily large graphs with ud⁡0∗(G)=c\operatorname{ud}^{*}_{0}(G)=c (Theorem 2). The case c=2c=2 shows that the constant 2 cannot be improved. Deciding whether ud⁡0∗(G)≥c\operatorname{ud}^{*}_{0}(G) \ge c is polynomial for every fixed cc (Theorem 7), whereas the threshold ⌈nc⌉\lceil\sqrt[c]{n}\rceil makes the problem NP-complete for every fixed c≥2c \ge2 (Theorem 8).

For the Non-Overlapping parameter, [5] proved the sharp bound ud⁡+∗(G)≥1+n−1\operatorname{ud}^{*}_{+}(G) \ge1+\sqrt{n-1}. We observe that their argument applies to every maximal 2-packing containing a vertex of maximum degree, so that a greedy polynomial-time construction attains the bound, and we show that deciding whether ud⁡+∗(G)≥4n\operatorname{ud}^{*}_{+}(G) \ge4\sqrt{n}, a threshold within a constant factor of that bound, is NP-complete even for split graphs (Theorem 9). Finally, we show that neither of the two constrained parameters bounds the other: there are graphs on which ud⁡+∗\operatorname{ud}^{*}_{+} exceeds ud⁡0∗\operatorname{ud}^{*}_{0} by an arbitrarily large factor, and trees on which the opposite holds (Theorems 10 and 11). Table 1 summarizes the results. Proofs of statements marked with ⋆\star are deferred to the appendix, except for the constructions of the two reductions.

Full-Cover ud⁡0∗(G)\operatorname{ud}^{*}_{0}(G)Non-Overlapping ud⁡+∗(G)\operatorname{ud}^{*}_{+}(G)
Earlier workintroduced here=F(G)= F(G) [1]
Lower bound≥2\ge2 (n≥2n \ge2), best possible≥1+n−1\ge1+\sqrt{n-1}, best possible [5]
Trees≥4n/5\ge4n/5, best possible≥8(n+2)−4\ge\sqrt{8(n+2)}-4, best possible [5]
Polynomialk=ck=c constantk=ck=c constant
NP-completek=⌈nc⌉k=\lceil\sqrt[c]{n}\rceil, c≥2c \ge2 fixedk=4nk=4\sqrt{n}, split graphs

Table 1. Summary of the results (entries with a reference are not proved here).

The Full-Cover Uni-domination Problem

Throughout this section SS is required to dominate every vertex, that is, V0(S)=∅V_{0}(S)=\varnothing, and the parameter is ud⁡0∗(G)\operatorname{ud}^{*}_{0}(G).

Structural Properties

Our first bound rests on the classical characterization of minimal dominating sets by private neighbors.

Theorem 1 (⋆\star). Every graph G=(V,E)G=(V,E) with ∣V∣≥2|V| \ge2 satisfies ud⁡0∗(G)≥2\operatorname{ud}^{*}_{0}(G) \ge2, and a dominating set SS with ud⁡(S)≥2\operatorname{ud}(S) \ge2 can be constructed in polynomial time.

Theorem 1 raises the question of the tightness of the constant 2. One might expect the number of uni-dominated vertices to grow with ∣V∣|V|, we show that under full coverage it can remain bounded by a constant.

Theorem 2 (⋆). For any integers c≥2c \ge2 and p≥1p \ge1, there exists a graph G=(V,E)G=(V,E) of order n=c+2pn=c+2p with ud⁡0∗(G)=c\operatorname{ud}_0^*(G)=c.

Proof (sketch). Given c≥2c \ge2 and p≥1p \ge1, we construct G=(V,E)G=(V,E) as follows. Let the vertex set VV be partitioned into two disjoint subsets: C={x1,…,xc}C=\{x_1,\ldots,x_c\} and R={u1,v1,…,up,vp}R=\{u_1,v_1,\ldots,u_p,v_p\}. We define the edge set EE such that there are no edges within CC, every vertex in CC is adjacent to every vertex in RR, and the induced subgraph on RR is a complete graph minus a perfect matching M={{ui,vi}∣1≤i≤p}M=\{\{u_i,v_i\}\mid1\le i\le p\}. Formally, E={xy:x∈C,y∈R}∪{xy:x,y∈R,x≠y}∖ME=\{xy:x\in C,y\in R\}\cup\{xy:x,y\in R,x\ne y\}\setminus M. Clearly, n=∣V∣=c+2pn=|V|=c+2p. The construction is illustrated in Figure 1.

Construction of G

Figure 1. Construction of GG such that ud⁡0∗(G)=c\operatorname{ud}_0^*(G)=c. Gray lines are edges and dashed lines are non-edges; the edges inside the shaded set RR are omitted.

The value cc is attained, for instance, by S=CS=C: every vertex of RR is dominated by all c≥2c\ge2 vertices of CC, while each vertex of the independent set CC is dominated by itself only, so that UD(S)=CUD(S)=C. Any set consisting of one vertex of CC and one vertex of RR is another optimal solution. For the upper bound, let SS be a dominating set. As GG has no universal vertex, ∣S∣≥2|S|\ge2. Every vertex of RR has exactly one non-neighbor, and is therefore dominated at least ∣S∣−1|S|-1 times. Hence, if ∣S∣≥3|S|\ge3, no vertex of RR is uni-dominated and ud⁡(S)≤∣C∣=c\operatorname{ud}(S)\le|C|=c. The dominating sets of size 2 are handled by a case analysis given in the appendix.

Trees

While Theorem 2 shows that ud⁡0∗(G)\operatorname{ud}_0^*(G) may be bounded by a constant in general graphs, on trees the situation is different: a constant fraction of the vertices can always be uni-dominated by a dominating set.

Theorem 3. Every tree TT of order nn satisfies ud⁡0∗(T)≥4n5\operatorname{ud}_0^*(T)\ge\frac{4n}{5}.

Proof. We proceed by induction on the order nn of the tree. Throughout the proof, the main cases are illustrated in Figure 2.

Figure 2. Overview of the main cases of the proof of Theorem 3.

We start with the small cases. The orders n≤2n \le2 are immediate. If n=3n = 3, the tree is a path and its central vertex uni-dominates all three vertices. If n=4n = 4, the tree is a path or a star, and in both cases it admits an efficient dominating set. Suppose now that n=5n = 5. There are three non-isomorphic trees of order 5. If TT is a star, its center uni-dominates every vertex. If TT is a path, two vertices at distance 3 uni-dominate every vertex. It remains to consider the tree HH obtained from K1,3K_{1,3} with center cc and leaves ℓ1,ℓ2,d\ell_1,\ell_2,d by subdividing the edge cdcd with a new vertex ee. The set S={c,d}S = \{c,d\} is dominating and it uni-dominates cc, ℓ1\ell_1, ℓ2\ell_2 and dd, while ee is dominated twice. Moreover, no subset of V(H)V(H) uni-dominates more than 4 vertices, so the bound 4/54/5 is tight. In all these small cases ud⁡∗(T)≥4n/5\operatorname{ud}^{*}(T) \ge4n/5.

Now let n≥6n \ge6 and assume that every tree of order less than nn satisfies the statement. Root TT at an arbitrary vertex rr and let hh be the height of the resulting rooted tree. If h≤1h \le1, then TT is a star and S={r}S = \{r\} uni-dominates all nn vertices. If h=2h = 2, let SS be the set of children of rr: every vertex is dominated, each child is uni-dominated by itself since two children of rr are never adjacent and no grandchild belongs to SS, and each grandchild is uni-dominated by its parent. Only rr may be dominated more than once, so ud⁡(S)≥n−1≥4n/5\operatorname{ud}(S) \ge n - 1 \ge4n/5 since n≥6n \ge6. We may therefore assume h≥3h \ge3. Let uu be a vertex of maximum depth. Since h≥3h \ge3, it has a parent vv, a grandparent ww and a great-grandparent xx. By maximality of the depth, uu is a leaf, every child of vv is a leaf, and every child of ww is either a leaf or a vertex all of whose children are leaves. Let TwT_w be the subtree rooted at ww and put k=∣V(Tw)∣≥3k = |V(T_w)| \ge3. The only edge joining TwT_w to the rest of TT is wxwx. Consequently Tr=T−V(Tw)T_r = T - V(T_w) is again a tree, of order n−k≥1n - k \ge1 since it contains xx. We distinguish three cases according to kk.

Case 1: k≥5k \ge5 (panel A of Figure 2). Let v1,…,vqv_1,\ldots,v_q be the children of ww, with v1=vv_1=v. By the choice of uu, every child of every viv_i is a leaf. By the induction hypothesis, TrT_r has a dominating set SrS_r with ud⁡(Sr)≥4(n−k)/5\operatorname{ud}(S_r) \ge4(n-k)/5. Put Sw={v1,…,vq}S_w=\{v_1,\ldots,v_q\} and S=Sr∪SwS=S_r\cup S_w. Each viv_i is uni-dominated by itself, since w∉Sww\notin S_w and none of its children belongs to SwS_w. Each child of viv_i is a leaf uni-dominated by viv_i. The vertex ww, being adjacent to all the q≥1q\ge1 vertices of SwS_w, is dominated but possibly more than once, so we do not count it. Hence SwS_w dominates TwT_w and uni-dominates at least k−1k-1 of its vertices. The two parts do not interfere: every vertex of SwS_w has all its neighbors inside TwT_w, so SwS_w dominates no vertex of TrT_r, and conversely ww is the only vertex of TwT_w with a neighbor outside TwT_w. Therefore SS is a dominating set of TT and, using k−1≥4k/5k-1\ge4k/5, we obtain ud⁡(S)≥4(n−k)/5+(k−1)≥4n/5\operatorname{ud}(S)\ge4(n-k)/5+(k-1)\ge4n/5.

Case 2: k=4k=4 (panels B1–B4 of Figure 2). Exactly two configurations are possible: either ww has a single child vv and vv has exactly two leaf children u1,u2u_1,u_2, or ww has exactly two children, namely vv with a single leaf child uu, and a leaf ℓ\ell. Here we remove xx as well: let R=V(T)∖(V(Tw)∪{x})R=V(T)\setminus(V(T_w)\cup\{x\}), so ∣R∣=n−5|R|=n-5. Since xx is removed, the forest T[R]T[R] may be disconnected. Let T1,…,TmT_1,\ldots,T_m be its components. Each is a tree of order less than nn, so the induction hypothesis provides a dominating set SiS_i of TiT_i with ud⁡(Si)≥4∣V(Ti)∣/5\operatorname{ud}(S_i)\ge4|V(T_i)|/5. Put S0=S1∪⋯∪SmS_0=S_1\cup\cdots\cup S_m. As no edge joins two components, S0S_0 dominates T[R]T[R] and uni-dominates at least 4(n−5)/54(n-5)/5 of its vertices. We choose Sw⊆V(Tw)S_w\subseteq V(T_w) according to whether xx is dominated by its neighbors in RR, that is, whether xx has a neighbor in S0S_0, and set S=S0∪SwS=S_0\cup S_w. Since S0⊆RS_0\subseteq R and Sw⊆V(Tw)S_w\subseteq V(T_w), we have x∉Sx\notin S.

Suppose first that xx is dominated by its neighbors in RR, as in panels B1 and B2. The vertex xx is then dominated, possibly several times, and we do not count it among the uni-dominated vertices. The four vertices of TwT_w, on the other hand, are all uni-dominated. In panel B1 we take Sw={v}S_w=\{v\}: the vertex vv is uni-dominated by itself, since none of u1,u2,wu_1,u_2,w lies in SwS_w, and u1,u2u_1,u_2 and ww are uni-dominated by vv, the only other neighbor of ww being x∉Sx\notin S. In panel B2 we take Sw={u,ℓ}S_w=\{u,\ell\}: the vertices uu and ℓ\ell are uni-dominated by themselves, vv is uni-dominated by uu, and ww by ℓ\ell, again because x∉Sx\notin S.

Suppose now that xx is not dominated by its neighbors in RR, as in panels B3 and B4. We then put ww in SwS_w, so that ww is uni-dominated by itself, since x∉Sx\notin S and v∉Swv\notin S_w, and xx is uni-dominated by ww, its only neighbor in SS. In panel B3 we take Sw={w,u1,u2}S_w=\{w,u_1,u_2\}: u1u_1 and u2u_2 are uni-dominated by themselves since v∉Swv\notin S_w, only vv is over-dominated, being adjacent to the three vertices of SwS_w. In panel B4 we take Sw={w,u}S_w=\{w,u\}: the vertex uu is uni-dominated by itself, ℓ\ell is uni-dominated by ww, only vv is over-dominated, being adjacent to both ww and uu.

In each of the four configurations every vertex of V(Tw)∪{x}V(T_w)\cup\{x\} is dominated and at least four of these five vertices are uni-dominated. Moreover every vertex of SwS_w has all its neighbors in V(Tw)∪{x}V(T_w)\cup\{x\}, so SwS_w dominates no vertex of RR. Conversely xx is the only vertex outside RR with a neighbor in RR, and xx is counted only in panels B3 and B4, where it has no neighbor in S0S_0. Hence SS is a dominating set of TT and ud⁡(S)≥4(n−5)/5+4=4n/5\operatorname{ud}(S)\ge4(n-5)/5+4=4n/5.

Case 3: k=3k=3. Here ww has a single child vv, which in turn has a single leaf child uu. By the induction hypothesis, the tree TrT_r, of order n−3n-3, has a dominating set SrS_r with ud⁡(Sr)≥4(n−3)/5\operatorname{ud}(S_r) \ge4(n-3)/5. This time the choice of SwS_w depends on whether xx belongs to SrS_r, the two resulting configurations being drawn in panels C1 and C2 of Figure 2. If x∈Srx \in S_r, take Sw={u}S_w=\{u\}: then uu is uni-dominated by itself, vv by uu since w∉Sww \notin S_w, and ww by xx since v,w∉Swv,w \notin S_w. If x∉Srx \notin S_r, take Sw={v}S_w=\{v\}: then vv uni-dominates uu, itself and ww, the latter because the only other neighbor of ww is x∉Sx \notin S. In both cases the three vertices of TwT_w are uni-dominated, and since N[u]⊆V(Tw)N[u] \subseteq V(T_w) and N[v]⊆V(Tw)N[v] \subseteq V(T_w), the set SwS_w dominates no vertex of TrT_r. Hence S=Sr∪SwS=S_r\cup S_w is a dominating set of TT and ud⁡(S)≥4(n−3)/5+3≥4n/5\operatorname{ud}(S) \ge4(n-3)/5+3 \ge4n/5.

In all cases we have exhibited a dominating set SS of TT with ud⁡(S)≥4n/5\operatorname{ud}(S) \ge4n/5, which completes the induction.

Since every dominating set is also an admissible set for unrestricted uni-domination, Theorem 3 immediately yields the same lower bound for ud⁡∗\operatorname{ud}^{*}. Moreover, the tree HH considered in the proof of Theorem 3 shows that the constant cannot be improved, even without the domination requirement.

Corollary 4. Every tree TT of order nn satisfies ud⁡∗(T)≥ud⁡0∗(T)≥4n5\operatorname{ud}^{*}(T) \ge\operatorname{ud}^{*}_{0}(T) \ge\frac{4n}{5}. Moreover, the constant 4/54/5 is best possible for both parameters.

Proof. The inequalities follow from Theorem 3 and ud⁡0∗(T)≤ud⁡∗(T)\operatorname{ud}^{*}_{0}(T) \le\operatorname{ud}^{*}(T). For sharpness, consider the tree HH in Figure 2. It has no efficient dominating set.

Corollary 4 answers Problem 1 of Hedetniemi and Rall [11]. We also note that [11] provides arbitrarily large trees for which no more than 4/54/5 of the vertices can be uni-dominated. Moreover, the proof of Theorem 3 is constructive, and its local reductions can be organized bottom-up so that every vertex and edge is processed a constant number of times.

Corollary 5 (⋆\star). For every tree TT of order nn, a dominating set SS of TT with ud⁡(S)≥4n5\operatorname{ud}(S) \ge\frac{4n}{5} can be computed in O(n)O(n) time.

Computational Complexity

We investigate the computational complexity of the Full-Cover Uni-domination (FCUD) problem, defined as follows.

Full-Cover Uni-domination (FCUD)
Instance: A graph G=(V,E)G=(V,E) and a positive integer kk.
Question: Is ud⁡0∗(G)≥k\operatorname{ud}^{*}_{0}(G) \ge k?

Table 1 (PDF p. 8).

The complexity of FCUD depends on the threshold kk. For a constant k=ck=c, the dominators of cc uni-dominated vertices CC form a core SCS_C of at most cc vertices, and adding every vertex outside N[C]N[C] keeps CC uni-dominated. It then suffices to test whether this expanded set dominates GG, as formalized in Lemma 6.

Lemma 6 (⋆\star). Let G=(V,E)G=(V,E) be a graph and c≥1c\ge1 be an integer. For any subset C⊆VC\subseteq V, let RC=V∖N[C]R_C=V\setminus N[C] be the set of vertices that are neither in CC nor adjacent to a vertex of CC. There exists a dominating set S⊆VS\subseteq V such that ud⁡(S)≥c\operatorname{ud}(S)\ge c if and only if there exist a target subset C⊆VC\subseteq V with ∣C∣=c|C|=c and a core subset SC⊆VS_C\subseteq V with ∣SC∣≤c|S_C|\le c satisfying the following conditions:

  1. C⊆UD(SC)C\subseteq UD(S_C).

  2. The expanded set S^=SC∪RC\widehat{S}=S_C\cup R_C is a dominating set of GG.

Because this lemma reduces the search space to subsets of size bounded by cc, we obtain a polynomial-time algorithm.

Theorem 7 (⋆\star). For any fixed integer c≥2c\ge2, given a graph G=(V,E)G=(V,E), the problem of deciding whether ud⁡0∗(G)≥c\operatorname{ud}_0^*(G)\ge c is solvable in polynomial time.

In contrast, when the threshold grows with the order of the graph, the problem becomes NP-complete.

Theorem 8 (⋆\star). For any fixed integer c≥2c\ge2, given a graph G=(V,E)G=(V,E), the problem of deciding whether ud⁡0∗(G)≥⌈nc⌉\operatorname{ud}_0^*(G)\ge\lceil\sqrt[c]{n}\rceil (where n=∣V∣n=|V|) is NP-complete.

Proof (sketch). The problem is in NP, as for a given subset S⊆VS\subseteq V one can check in polynomial time whether V0(S)=∅V_0(S)=\varnothing and ud⁡(S)≥⌈nc⌉\operatorname{ud}(S)\ge\lceil\sqrt[c]{n}\rceil. To prove NP-hardness, we perform a polynomial-time reduction from RX3C. The reduction is described below.

Let I=(X,C)I=(X,\mathcal{C}) be an instance of RX3C, so that ∣X∣=∣C∣=3p|X|=|\mathcal{C}|=3p, and set y=10p+2y=10p+2. We construct GG as the disjoint union of three graphs G1G_1, G2G_2 and G3G_3. The part G1G_1 encodes the instance II, G2G_2 adds pp vertices so that ∣V(G1)∣+∣V(G2)∣=10p|V(G_1)|+|V(G_2)|=10p is even, which makes the order of G3G_3 even, and G3G_3 is a padding part whose contribution to the uni-domination is a controlled constant and whose size brings the order of GG to a cc-th power.

  • Part G1G_1: We create three layers of vertices. The bottom layer consists of 3p3p vertices representing the elements x∈Xx\in X. The middle layer consists of 3p3p vertices representing the subsets Cj∈CC_j\in\mathcal{C}. We add an edge between a

vertex representing an element xx and a vertex representing a subset CjC_j if and only if x∈Cjx \in C_j. Finally, the top layer consists of 3p3p pendant vertices L={lj:1≤j≤3p}L = \{l_j : 1 \le j \le3p\}, the leaf ljl_j being adjacent to the subset vertex CjC_j only. Thus ∣V(G1)∣=9p|V(G_1)| = 9p.

  • Part G2G_2: We construct a complete graph KpK_p on exactly pp vertices. Thus ∣V(G2)∣=p|V(G_2)| = p.

  • Part G3G_3: Let NM=yc−10pN_M = y^c - 10p. Since y=10p+2y = 10p + 2 is even, ycy^c is even, and as 10p10p is even, NMN_M is an even integer. Moreover yc≥(10p+2)2>10py^c \ge(10p + 2)^2 > 10p, so NM≥2N_M \ge2. We let G3G_3 be a complete graph on NMN_M vertices minus a perfect matching, that is, V(G3)={r1,r1′,…,rm,rm′}V(G_3) = \{r_1,r'_1,\ldots,r_m,r'_m\} where m=NM/2m = N_M/2, all pairs of vertices being adjacent except the pairs riri′r_i r'_i.

The construction is illustrated in Figure 3. The total number of vertices of GG is 9p+p+(yc−10p)=yc9p + p + (y^c - 10p) = y^c, so the required threshold is ⌈nc⌉=y=10p+2\lceil\sqrt[c]{n} \rceil= y = 10p + 2. Since cc is fixed and the numbers of vertices and edges of GG are bounded by a polynomial in pp, this instance is constructed in polynomial time in the size of II. It remains to prove that II has an exact cover if and only if GG admits a dominating set SS with ud⁡(S)≥10p+2\operatorname{ud}(S) \ge10p + 2 (see the appendix).

Construction of graph G, showing the disjoint union of G1, G2 and G3

Figure 3. The construction of graph GG, the disjoint union of G1G_1, G2G_2 and G3G_3. Gray lines are edges and dashed lines are non-edges; the edges of G3G_3 are omitted.

The Non-Overlapping Uni-domination Problem

Throughout this section V+(S)=∅V_{+}(S) = \varnothing. Every vertex it dominates is then dominated exactly once, so ud⁡(S)=I(S)=∑v∈S(1+deg⁡(v))\operatorname{ud}(S) = I(S) = \sum_{v \in S}(1 + \deg(v)).

Structural Properties

Unlike the full-cover variant, which may be bounded by a constant, the non-overlapping constraint yields a number of uni-dominated vertices that always scales with the order of the graph. Goddard, Oellermann, Slater and Swart [5] proved the sharp bound ud⁡+∗(G)≥1+n−1\operatorname{ud}^{*}_{+}(G) \ge1 + \sqrt{n - 1} for every graph of order nn, and exhibited graphs of diameter 2 obtained from projective planes for which ud⁡+∗(G)=⌈1+n−1⌉\operatorname{ud}^{*}_{+}(G) = \lceil1 + \sqrt{n - 1} \rceil.

We record one observation about that bound. Their argument starts from a 2-packing of maximum influence, but the proof of the two inequalities it combines, ud⁡+∗(G)≥1+Δ\operatorname{ud}^{*}_{+}(G) \ge1 + \Delta and ud⁡+∗(G)≥n(Δ+1)/(Δ2+1)\operatorname{ud}^{*}_{+}(G) \ge n(\Delta+ 1)/(\Delta^2 + 1), uses only that the 2-packing under consideration contains a vertex of maximum degree and is maximal, respectively: a maximal 2-packing SS satisfies N[N[S]]=VN[N[S]] = V, which is all that the counting argument requires. A maximal 2-packing containing a vertex of maximum degree is obtained in polynomial time by starting from S={v}S = \{v\} with deg⁡(v)=Δ\deg(v) = \Delta and, as long as some vertex is at distance at least 3 from every vertex of SS, adding such a vertex to SS. As the first bound is increasing and the second one is decreasing in Δ≥1\Delta\ge1, and the two coincide at Δ=n−1\Delta= \sqrt{n - 1}, their maximum is at least 1+n−11 + \sqrt{n - 1} for every Δ\Delta. Hence such a set SS already satisfies ud⁡(S)≥1+n−1\operatorname{ud}(S) \ge1 + \sqrt{n - 1}, so the bound of [5] is attained constructively.

No lower bound linear in nn holds, even on trees: the same authors proved the sharp bound ud⁡+∗(T)≥8(n+2)−4\operatorname{ud}^{*}_{+}(T) \ge\sqrt{8(n + 2)} - 4 for every tree of order nn, together with an extremal family attaining it [5]. The contrast with Theorem 3, which guarantees 4n/54n/5 uni-dominated vertices on every tree under full coverage, is the sharpest illustration of how differently the two constraints behave.

Computational Complexity

We consider the following decision problem.

Non-Overlapping Uni-domination
Instance: A graph G=(V,E)G=(V,E) and a positive integer kk.
Question: Is ud⁡+∗(G)≥k\operatorname{ud}^{*}_{+}(G)\ge k?

Table 1 (PDF p. 11).

For a fixed constant threshold k=ck=c, the answer is positive whenever n≥(c−1)2+1n\ge(c-1)^2+1, by the bound ud⁡+∗(G)≥1+n−1\operatorname{ud}^{*}_{+}(G)\ge1+\sqrt{n-1} recalled above, and the remaining instances have bounded order, so they are settled by exhaustive search in constant time. We show that raising the threshold by a constant factor, from 1+n−11+\sqrt{n-1} to 4n4\sqrt{n}, already makes the problem NP-complete on split graphs.

Theorem 9 (⋆). Given a graph GG with nn vertices, the problem of deciding whether ud⁡+∗(G)≥4n\operatorname{ud}^{*}_{+}(G)\ge4\sqrt{n} is NP-complete, even for split graphs.

Proof (sketch). The problem is in NP, as verifying whether a given subset S⊆VS\subseteq V satisfies V+(S)=∅V_{+}(S)=\varnothing and ud⁡(S)≥4n\operatorname{ud}(S)\ge4\sqrt{n} can be done in polynomial time. To prove NP-hardness, we present a polynomial-time reduction from the RX3C problem. Let I=(X,C)I=(X,C) be an instance of RX3C, with ∣X∣=3p|X|=3p and C={C1,…,C3p}C=\{C_1,\ldots,C_{3p}\}. Instances with p≤7p\le7 have bounded size and are solved in constant time, so we may assume p≥8p\ge8.

We construct G=(V,E)G=(V,E) as follows. Each element of XX becomes a vertex, and XX is turned into a clique of size 3p3p. Each subset Ci∈CC_i\in C receives a gadget consisting of an independent set of sis_i vertices, each of them joined to the three vertices of XX corresponding to the elements of CiC_i. Since VV is partitioned into the clique XX and the independent set of all gadget vertices, GG is a split graph.

The construction is illustrated in Figure 4, and the sizes sis_i are chosen so that the order nn of GG equals p2p^2. Let q=⌊p/3⌋q = \lfloor p/3 \rfloor, and note that q≥2q \ge2 because p≥8p \ge8, so every gadget receives at least one vertex. If p=3qp = 3q, set si=q−1s_i = q - 1 for all 3p3p gadgets, so that n=3p+3p(q−1)=3pq=p2n = 3p + 3p(q - 1) = 3pq = p^2. If p=3q+1p = 3q + 1, set si=qs_i = q for exactly pp gadgets and si=q−1s_i = q - 1 for the other 2p2p, so that n=3p+pq+2p(q−1)=p+3pq=p2n = 3p + pq + 2p(q - 1) = p + 3pq = p^2. If p=3q+2p = 3q + 2, set si=qs_i = q for exactly 2p2p gadgets and si=q−1s_i = q - 1 for the other pp, so that n=3p+2pq+p(q−1)=2p+3pq=p2n = 3p + 2pq + p(q - 1) = 2p + 3pq = p^2. In all three cases n=p2n = p^2, so p=np = \sqrt{n} and the required threshold is 4p=4n4p = 4\sqrt{n}. So GG has p2p^2 vertices and O(p2)O(p^2) edges, hence is built in polynomial time. It remains to prove that II has an exact cover if and only if GG admits a 2-packing SS with ud⁡(S)≥4p\operatorname{ud}(S) \ge4p (see the appendix).

Graph built from an RX3C instance

Figure 4. The graph GG built from an RX3C instance in the proof of Theorem 9. The shaded rectangle is the clique XX, whose edges are omitted, and dots stand for omitted vertices.

Comparison of the Two Variants

We now show that neither parameter bounds the other, by exhibiting a family of graphs for each direction.

The first one consists of the complete graphs of even order n≥4n \ge4 minus a perfect matching, on which ud⁡+∗\operatorname{ud}^{*}_{+} exceeds ud⁡0∗\operatorname{ud}^{*}_{0} by a factor of order nn.

Theorem 10 (⋆). For every even integer n≥4n \ge4, there exists a graph G=(V,E)G = (V,E) of order nn such that 2=ud⁡0∗(G)<ud⁡+∗(G)=n−12 = \operatorname{ud}^{*}_{0}(G) < \operatorname{ud}^{*}_{+}(G) = n - 1.

The second family consists of trees. For an integer p≥3p \ge3, we construct a tree Tp=(V,E)T_p = (V,E) as follows: create a root vertex rr; create pp star graphs A1,A2,…,ApA_1, A_2, \ldots, A_p, where each star AiA_i consists of a center vertex rir_i and p−1p - 1 leaves; add an edge between the root rr and each center rir_i. We set T={Tp:p≥3}\mathcal{T} = \{T_p : p \ge3\}. The restriction p≥3p \ge3 is necessary: the same construction with p=2p = 2 produces the path P5P_5, which admits an efficient dominating set, so that both parameters equal nn and no separation occurs. The following theorem shows that on these trees the full-cover parameter exceeds the non-overlapping one by a factor of order n\sqrt{n}.

Theorem 11 (⋆). Every tree Tp∈TT_p \in\mathcal{T} has order n=p2+1n = p^2 + 1 and satisfies 3n−1−1=ud⁡+∗(Tp)<ud⁡0∗(Tp)=n−13\sqrt{n - 1} - 1 = \operatorname{ud}^{*}_{+}(T_p) < \operatorname{ud}^{*}_{0}(T_p) = n - 1.

Conclusion and Open Problems

We studied two restricted variants of the uni-domination problem, which measure how closely a graph can approach efficient domination when one of the two possible defects is forbidden. Besides the linear-time bound ud⁡0∗(T)≥4n/5\operatorname{ud}^{*}_{0}(T) \ge4n/5 on trees, which answers Problem 1 of [11], we showed that the two variants differ sharply, both in their lower bounds and in the thresholds at which their decision problems become NP-complete, and that neither of them bounds the other.

A quantitative gap remains for the non-overlapping variant: every graph satisfies ud⁡+∗(G)≥1+n−1\operatorname{ud}^{*}_{+}(G) \ge1 + \sqrt{n - 1}, and this is sharp, yet deciding whether ud⁡+∗(G)≥4n\operatorname{ud}^{*}_{+}(G) \ge4\sqrt{n} is NP-complete, so that the complexity of the intermediate thresholds ud⁡+∗(G)≥cn\operatorname{ud}^{*}_{+}(G) \ge c\sqrt{n} with 1<c<41 < c < 4 is unknown. It would be interesting to tighten this gap, and to study these parameters, algorithmically and structurally, on graph classes such as planar or chordal graphs and their subclasses.

Acknowledgments

Acknowledgments. This work was supported by the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25.

Proofs for Section 2 (The Full-Cover Uni-domination Problem)

Theorem 1 (⋆\star). Every graph G=(V,E)G=(V,E) with ∣V∣≥2|V|\ge2 satisfies ud⁡0∗(G)≥2\operatorname{ud}^{\ast}_{0}(G)\ge2, and a dominating set SS with ud⁡(S)≥2\operatorname{ud}(S)\ge2 can be constructed in polynomial time.

Proof. We first observe that every minimal dominating set SS of GG satisfies ud⁡(S)≥∣S∣\operatorname{ud}(S)\ge|S|. Indeed, a dominating set is minimal if and only if it is irredundant [4, 9], so every v∈Sv\in S has a private neighbor pvp_v with respect to SS, that is, a vertex with N[pv]∩S={v}N[p_v]\cap S=\{v\}. In particular pv∈UD(S)p_v\in UD(S). If pu=pvp_u=p_v for two distinct u,v∈Su,v\in S, then {u}=N[pu]∩S=N[pv]∩S={v}\{u\}=N[p_u]\cap S=N[p_v]\cap S=\{v\}, a contradiction, so the mapping v↦pvv\mapsto p_v is injective and ud⁡(S)≥∣S∣\operatorname{ud}(S)\ge|S|.

Now assume ∣V∣≥2|V|\ge2. A minimal dominating set is obtained in polynomial time by a standard greedy reduction: initialize S=VS=V and remove a vertex vv from SS whenever S∖{v}S\setminus\{v\} still dominates GG. One pass over the vertices suffices, and the resulting set SS is a minimal dominating set, so ud⁡(S)≥∣S∣\operatorname{ud}(S)\ge|S| by the observation above. If ∣S∣≥2|S|\ge2, we obtain ud⁡(S)≥2\operatorname{ud}(S)\ge2. If ∣S∣=1|S|=1, say S={u}S=\{u\}, then uu dominates GG on its own and is therefore a universal vertex, so UD(S)=VUD(S)=V and ud⁡(S)=∣V∣≥2\operatorname{ud}(S)=|V|\ge2. In both cases the polynomially constructed dominating set SS is a witness for ud⁡0∗(G)≥2\operatorname{ud}^{\ast}_{0}(G)\ge2. □

Lemma 12. Let G=(V,E)G=(V,E) be a graph and let u∈Vu\in V have exactly kk non-neighbors in GG. For any subset S⊆VS\subseteq V with ∣S∣≥k+2|S|\ge k+2, the vertex uu is not uni-dominated by SS.

Proof. Write N‾(u)=V∖N[u]\overline{N}(u)=V\setminus N[u] for the set of the non-neighbors of uu, so that ∣N‾(u)∣=k|\overline{N}(u)|=k. Since VV is the disjoint union of N[u]N[u] and N‾(u)\overline{N}(u), the number of times uu is dominated by SS equals ∣S∩N[u]∣=∣S∖N‾(u)∣≥∣S∣−k≥2|S\cap N[u]|=|S\setminus\overline{N}(u)|\ge|S|-k\ge2. Hence u∈V+(S)u\in V_{+}(S) and uu is not uni-dominated. □

Theorem 2 (⋆\star). For any integers c≥2c\ge2 and p≥1p\ge1, there exists a graph G=(V,E)G=(V,E) of order n=c+2pn=c+2p with ud⁡0∗(G)=c\operatorname{ud}^{\ast}_{0}(G)=c.

Proof. Let GG be the graph constructed in the main text and illustrated in Figure 1, its order is c+2pc+2p. By construction, there are no edges between any two vertices in CC, making CC an independent set of size cc. Every vertex in CC is non-adjacent only to the other c−1c-1 vertices within CC. Meanwhile, every vertex in RR is connected to all vertices in CC and all vertices in RR except its unique non-neighbor. Thus, every vertex in RR has exactly one non-neighbor in GG.

Let SS be a dominating set of GG. Since GG has no universal vertex, we must have ∣S∣≥2|S|\ge2. We evaluate ud⁡(S)\operatorname{ud}(S) based on the cardinality of SS:

  • Case 1: ∣S∣≥3|S|\ge3. For any vertex v∈Rv\in R, its number of non-neighbors is exactly one. By Lemma 12 applied with k=1k=1, since ∣S∣≥3|S|\ge3, no vertex in RR can be uni-dominated. Consequently, UD(S)⊆CUD(S)\subseteq C. Since ∣C∣=c|C|=c, it follows that ud⁡(S)=∣UD(S)∣≤c\operatorname{ud}(S)=|UD(S)|\le c.

  • Case 2: ∣S∣=2|S|=2. Let S={y,z}S=\{y,z\}. We analyze the possible configurations of SS:

  • If y,z∈Cy,z\in C: since CC is an independent set, neither yy nor zz dominates the other, and no vertex of C∖{y,z}C\setminus\{y,z\} is adjacent to either of them. Two sub-cases arise. If c>2c>2, then any x∈C∖{y,z}x\in C\setminus\{y,z\} satisfies x∈V0(S)x\in V_0(S), so SS is not a dominating set and this configuration does not occur. If c=2c=2, then S=CS=C: every vertex of RR is adjacent to both yy and zz, hence is dominated twice, while yy and zz are each dominated by themselves only. Consequently UD(S)=CUD(S)=C and ud⁡(S)=2=c\operatorname{ud}(S)=2=c.

  • If y∈Cy\in C and z∈Rz\in R: Since yy and zz are adjacent, they dominate each other, meaning y,z∈V+(S)y,z\in V_+(S). For the remaining vertices, any vertex in C∖{y}C\setminus\{y\} is adjacent to zz but not yy, so it is dominated exactly once. For vertices in R∖{z}R\setminus\{z\}, they are all adjacent to yy. They are also adjacent to zz, except for the unique non-neighbor z′z' of zz. Thus, z′z' is only dominated by yy, so z′∈UD(S)z'\in UD(S). This yields UD(S)=(C∖{y})∪{z′}UD(S)=(C\setminus\{y\})\cup\{z'\}, giving exactly ud⁡(S)=(c−1)+1=c\operatorname{ud}(S)=(c-1)+1=c.

  • If y,z∈Ry,z\in R: First, since every vertex in RR is adjacent to all vertices in CC, SS covers CC. Second, within RR, every vertex has exactly one non-neighbor. Since SS contains two distinct vertices yy and zz, the only vertex not dominated by yy is its unique non-neighbor, which is necessarily dominated by zz, and vice versa. Thus, the entire graph is dominated (V0(S)=∅V_0(S)=\varnothing). Furthermore, because both yy and zz are adjacent to all of CC, every vertex in CC is dominated exactly twice, meaning UD(S)⊆RUD(S)\subseteq R. Since the non-edges of RR form the perfect matching MM, UD(S)UD(S) will contain exactly two vertices (either yy and zz if yz∉Eyz\notin E, or their respective unique non-neighbors if yz∈Eyz\in E). Thus, ud⁡(S)=2≤c\operatorname{ud}(S)=2\leq c.

Therefore, for any dominating set of size 2, we have ud⁡(S)≤c\operatorname{ud}(S)\leq c.

From both cases, we establish that ud⁡(S)≤c\operatorname{ud}(S)\leq c for any dominating set SS. This upper bound is achievable through two distinct structural configurations. As shown in Case 2, any dominating set consisting of exactly one vertex of CC and one vertex of RR yields exactly ud⁡(S)=c\operatorname{ud}(S)=c. The second one is S=CS=C, already met in Case 2 for c=2c=2 and available for every c≥2c\geq2: since p≥1p\geq1, every vertex of RR is adjacent to all c≥2c\geq2 vertices of CC, so R⊆V+(S)R\subseteq V_+(S), and since CC is an independent set, each vertex of CC is dominated by itself only. No vertex is left undominated (V0(S)=∅V_0(S)=\varnothing) and UD(S)=CUD(S)=C, which again yields ud⁡(S)=c\operatorname{ud}(S)=c. Having established both the upper bound and its attainability, we conclude that ud⁡0∗(G)=c\operatorname{ud}_0^*(G)=c.

Corollary 5 (⋆). For every tree TT of order nn, a dominating set SS of TT with ud⁡(S)≥4n5\operatorname{ud}(S)\geq\frac{4n}{5} can be computed in O(n)O(n) time.

Proof. We turn the induction of Theorem 3 into a bottom-up peeling procedure. The difference with a direct recursive implementation is that the tree is rooted only once and that no traversal is recomputed after a deletion.

Initialization. Root TT at an arbitrary vertex rr. One traversal computes, for every vertex, its parent, its list of children and its depth, and groups the vertices into buckets D0,D1,…D_0,D_1,\ldots by depth. Every vertex is marked active, and we maintain the number of active vertices. Depths are never recomputed: they are those of the initial rooting.

Invariant. The active vertices always induce a subtree of TT containing rr, which we call the active tree, because each step deletes a whole rooted subtree of it. Consequently the depth of an active vertex in the active tree is its depth in TT, and the height of the active tree is the largest depth of an active vertex.

One step. Let uu be an active vertex of maximum depth. If at most 5 vertices are active, or if depth⁡(u)≤2\operatorname{depth}(u) \le2, the active tree is terminal and is treated as described below. Otherwise uu has a parent vv, a grandparent ww and a great-grandparent xx, all active. We let TwT_w be the active subtree rooted at ww and k=∣V(Tw)∣k = |V(T_w)|. Deleted vertices are grouped into bags: some bags are determined at once, the others store a rule depending on the membership in SS of a single active vertex, to which the bag is then attached. The three cases of Theorem 3 are handled as follows.

Case k≥5k \ge5. The bag is V(Tw)V(T_w) and the choice Sw={v1,…,vq}S_w = \{v_1,\ldots,v_q\}, where v1,…,vqv_1,\ldots,v_q are the active children of ww, is fixed immediately. By Case 1 of Theorem 3 every vertex of the bag is dominated, at least k−1≥4k/5k-1 \ge4k/5 of them are uni-dominated, and no vertex of SwS_w has a neighbor outside the bag.

Case k=3k = 3. The bag is V(Tw)={w,v,u}V(T_w) = \{w,v,u\}, it is attached to xx and stores the rule of Case 3 of Theorem 3, namely Sw={u}S_w = \{u\} if x∈Sx \in S and Sw={v}S_w = \{v\} if x∉Sx \notin S. Under both alternatives w∉Sww \notin S_w, so no vertex of the bag dominates xx, and all three vertices of the bag are uni-dominated.

Case k=4k = 4. Here Q=V(Tw)∪{x}Q = V(T_w) \cup\{x\} has order 5, and we delete the whole active subtree rooted at xx, that is, QQ together with the subtrees rooted at the active children of xx other than ww, we call the latter the side components. Since uu has maximum depth, every active vertex has depth at most depth⁡(x)+3\operatorname{depth}(x) + 3, so a side component, whose root has depth depth⁡(x)+1\operatorname{depth}(x) + 1, has height at most 2. Each side component is therefore solved at once: if its order is at most 5 we use a base case of Theorem 3, otherwise we select its root if its height is at most 1, and the children of its root if its height is 2. In every case the component is dominated and at least a 4/54/5 fraction of its vertices is uni-dominated: in the base cases by Theorem 3, and otherwise because the selected vertices uni-dominate every vertex of the component except possibly its root, which gives at least n′−1≥4n′/5n' - 1 \ge4n'/5 uni-dominated vertices for a component of order n′≥6n' \ge6. As the only neighbor of a side component outside it is xx, and xx never belongs to the set chosen inside QQ, these components require no later decision.

Scanning the roots of the side components tells us whether xx already has a selected neighbor below it. If it does, the corresponding choice of Case 2 of Theorem 3 for a vertex xx having a neighbor in S0S_0 is fixed at once. Otherwise the only neighbor of xx outside QQ whose status is still undecided is its parent pp, and the bag QQ is attached to pp: the first choice if p∈Sp \in S, the second one if p∉Sp \notin S. If x=rx = r there is no such pp; the second choice is fixed at once, and the deletion of the subtree rooted at xx empties the active tree, so that only the propagation phase remains. In all cases x∉Swx \notin S_w, so the bag does not dominate pp. Every vertex of QQ is dominated and at least four of them are uni-dominated.

Terminal step. When at most 5 vertices are active, we solve the active tree by the corresponding base case of Theorem 3. When it has height at most 2 and order at least 6, we select its root if its height is at most 1, and the children of its root if its height is 2, as in the treatment of the heights h≤1h \le1 and h=2h = 2 in the induction step of Theorem 3. In both situations the active tree is dominated, at least 4/54/5 of its vertices are uni-dominated, and all of them become decided.

Propagation. Each bag is attached to a vertex that is still active when the bag is created, hence deleted strictly later. The dependencies are therefore directed towards the root and are acyclic. When the status of a vertex zz becomes known, every bag attached to zz is resolved, which fixes the status of its vertices and may in turn resolve further bags. The terminal step fixes the status of the last undecided vertices and triggers the resolution of all the remaining bags.

Correctness. The bags, the side components and the terminal component partition V(T)V(T). A bag of the case k≥5k \ge5 contributes at least k−1≥4k/5k - 1 \ge4k/5 uni-dominated vertices out of kk, a bag of the case k=4k = 4 at least 4 out of 5, a bag of the case k=3k = 3 exactly 3 out of 3, and each side component as well as the terminal component at least a 4/54/5 fraction of its vertices. Summing gives ud⁡(S)≥4n/5\operatorname{ud}(S) \ge4n/5, provided that no choice destroys the domination counted in another part. This is the content of Theorem 3, transposed as follows. In the case k≥5k \ge5 the only vertex of the bag with a neighbor outside it is ww, which is not counted, and no vertex of SwS_w has a neighbor outside the bag. In the case k=3k = 3 the only outside neighbor is xx, and the rule stored in the bag distinguishes the two possible statuses of xx. In the case k=4k = 4 the only vertex of QQ with neighbors outside QQ is xx, and the rule again distinguishes the two possible statuses of the outside neighbors of xx.

It remains to check that postponing the decision of a bag creates no conflict. Let QQ be a bag attached to a vertex zz. Whichever of its two alternatives is eventually chosen, the vertex of QQ adjacent to zz, namely ww in the case k=3k = 3 and xx in the case k=4k = 4, is not selected. Hence QQ contributes no selected neighbor to zz, so the domination status of zz, and of every vertex that is still active, does not depend on QQ, and the active tree can be processed as if QQ had been removed. Conversely, when QQ is created, zz is the only vertex with a neighbor in QQ whose membership in SS is still undecided, and the rule stored in QQ prescribes a correct choice both for z∈Sz \in S and for z∉Sz \notin S. Therefore, once all bags are resolved, every vertex of TT is dominated, and every vertex counted in a bag is uni-dominated by the final set SS.

Running time. The initialization takes O(n)O(n) time. To find an active vertex of maximum depth we scan the buckets DdD_d from the largest index downwards, keeping a pointer made of the current bucket index and of a position inside that bucket. Neither component ever moves backwards, which is legitimate because the largest depth of an active vertex never increases and because a vertex passed over is deleted. Each vertex is thus skipped at most once, so all these searches cost O(n)O(n) in total. When ww is processed, its children and grandchildren are scanned in order to build TwT_w, and TwT_w is then deleted. In the case k=4k = 4 the children of xx are scanned once and xx is deleted, and each side component is traversed only when it is deleted. Every vertex and every edge is thus examined a constant number of times. Finally each bag is created once and resolved once, and each dependency is processed once. Since ∣E(T)∣=n−1|E(T)| = n - 1, the total running time is O(n)O(n), and the algorithm uses O(n)O(n) space.

Lemma 6 (⋆). Let G=(V,E)G = (V, E) be a graph and c≥1c \ge1 be an integer. For any subset C⊆VC \subseteq V, let RC=V∖N[C]R_C = V \setminus N[C] be the set of vertices that are neither in CC nor adjacent to a vertex of CC. There exists a dominating set S⊆VS \subseteq V such that ud⁡(S)≥c\operatorname{ud}(S) \ge c if and only if there exist a target subset C⊆VC \subseteq V with ∣C∣=c|C| = c and a core subset SC⊆VS_C \subseteq V with ∣SC∣≤c|S_C| \le c satisfying the following conditions:

  1. C⊆UD(SC)C \subseteq UD(S_C).

  2. The expanded set S^=SC∪RC\widehat{S} = S_C \cup R_C is a dominating set of GG.

Proof. (⇒) Assume there exists a dominating set SS of GG with ud⁡(S)≥c\operatorname{ud}(S) \ge c. We can choose a target subset C⊆UD(S)C \subseteq UD(S) of exactly cc uni-dominated vertices. Let SC=S∩N[C]S_C = S \cap N[C]. By definition, N[C]=⋃u∈CN[u]N[C] = \bigcup_{u \in C} N[u], which allows us to distribute the intersection: SC=⋃u∈C(S∩N[u])S_C = \bigcup_{u \in C}(S \cap N[u]). Because each u∈Cu \in C is uni-dominated by SS, the intersection S∩N[u]S \cap N[u] contains exactly one vertex. Since N[u]⊆N[C]N[u] \subseteq N[C], this unique dominator belongs to S∩N[C]S \cap N[C], which is exactly SCS_C. Thus, SCS_C dominates uu. Furthermore, because SC⊆SS_C \subseteq S and SS uni-dominates uu, SCS_C cannot dominate uu more than once. Therefore, SCS_C uni-dominates uu, yielding C⊆UD(SC)C \subseteq UD(S_C). Additionally, since SCS_C is the union of exactly cc singleton sets, its cardinality is bounded by ∣SC∣≤c|S_C| \le c.

Next, we show that the expanded set S^=SC∪RC\widehat{S} = S_C \cup R_C is a dominating set of GG. Consider an arbitrary vertex v∈Vv \in V. We distinguish two cases:

  • Case 1: v∈RCv \in R_C. By the construction of S^\widehat{S}, vv is directly included in S^\widehat{S}, meaning it is dominated by itself.

  • Case 2: v∈N[C]v \in N[C]. Since the original set SS is a dominating set of GG, vv must be dominated by some vertex w∈Sw \in S. We consider where ww lies:

    • Subcase 2.1: w∈N[C]w \in N[C]. Because w∈Sw \in S and w∈N[C]w \in N[C], ww belongs to their intersection. By our earlier definition SC=S∩N[C]S_C = S \cap N[C], which directly implies w∈SCw \in S_C. Since SC⊆S^S_C \subseteq\widehat{S}, the vertex ww is present in S^\widehat{S}.

    • Subcase 2.2: w∉N[C]w \notin N[C]. By the definition of the remaining set RC=V∖N[C]R_C = V \setminus N[C], any vertex not in N[C]N[C] must belong to RCR_C. Thus, w∈RCw \in R_C. Since RC⊆S^R_C \subseteq\widehat{S}, the vertex ww is again present in S^\widehat{S}.

In all scenarios, the vertex responsible for dominating vv is guaranteed to be in S^\widehat{S}, proving that S^\widehat{S} is indeed a dominating set.

(⇐) Assume such subsets CC and SCS_C exist. By condition 2, S^=SC∪RC\widehat{S} = S_C \cup R_C is a dominating set of GG. Consider an arbitrary vertex u∈Cu \in C. Since u∈Cu \in C, we have N[u]⊆N[C]N[u] \subseteq N[C], and therefore N[u]N[u] is disjoint from RC=V∖N[C]R_C = V \setminus N[C]. Therefore, the intersection of its closed neighborhood with the expanded set S^\widehat{S} simplifies to N[u]∩S^=N[u]∩(SC∪RC)=N[u]∩SCN[u] \cap\widehat{S} = N[u] \cap(S_C \cup R_C) = N[u] \cap S_C. By condition 1, uu is uni-dominated by SCS_C, meaning ∣N[u]∩SC∣=1|N[u] \cap S_C| = 1. This implies ∣N[u]∩S^∣=1|N[u] \cap\widehat{S}| = 1. Because this unique domination property holds for every single vertex u∈Cu \in C, every such vertex is uni-dominated by S^\widehat{S}. Consequently, the entire target set CC is contained in UD(S^)UD(\widehat{S}). Given that ∣C∣=c|C| = c, we conclude that ud⁡(S^)≥c\operatorname{ud}(\widehat{S}) \ge c.

Theorem 7 (⋆). For any fixed integer c≥2c \ge2, given a graph G=(V,E)G=(V,E), the problem of deciding whether ud⁡0∗(G)≥c\operatorname{ud}^{*}_{0}(G) \ge c is solvable in polynomial time.

Proof. Given a graph G=(V,E)G=(V,E) with n=∣V∣n=|V| and a fixed integer c≥2c \ge2, we algorithmically verify if ud⁡0∗(G)≥c\operatorname{ud}^{*}_{0}(G) \ge c by applying the expansion logic from Lemma 6:

  1. Generate all possible target subsets C⊆VC \subseteq V of size exactly cc one by one.

  2. Generate all possible core subsets SC⊆VS_C \subseteq V of size at most cc one by one.

  3. For each pair (C,SC)(C,S_C), check if SCS_C uni-dominates CC. If it does, expand SCS_C into S^=SC∪RC\widehat{S}=S_C \cup R_C (where RC=V∖N[C]R_C=V \setminus N[C]). Check if this expanded set S^\widehat{S} dominates the entire graph GG.

  4. If any pair successfully produces a global dominating set, return TRUE. If all combinations fail, return FALSE.

To establish the time complexity, observe that since cc is fixed, the number of target subsets CC generated in Step 1 is (nc)=O(nc)\binom{n}{c}=O(n^c). Similarly, the number of core subsets SCS_C generated in Step 2 is bounded by ∑i=1c(ni)\sum_{i=1}^{c}\binom{n}{i}, which is also O(nc)O(n^c). The algorithm therefore evaluates at most O(n2c)O(n^{2c}) pairs of (C,SC)(C,S_C). Inside the loop, for each pair, isolating the non-adjacent set RCR_C, verifying the local uni-domination on CC, and confirming the global domination of S^\widehat{S} can all be executed in O(n2)O(n^2) time. The overall worst-case time complexity is bounded by O(n2c+2)O(n^{2c+2}). This running time is polynomial, which concludes the proof. □\square

Theorem 8 (⋆). For any fixed integer c≥2c \ge2, given a graph G=(V,E)G=(V,E), the problem of deciding whether ud⁡0∗(G)≥⌈nc⌉\operatorname{ud}^{*}_{0}(G) \ge\lceil\sqrt[c]{n}\rceil (where n=∣V∣n=|V|) is NPNP-complete.

Proof. We use the notation of the reduction described in § 2.3, and prove that the RX3C instance II has an exact cover if and only if GG admits a dominating set SS with ud⁡(S)≥10p+2\operatorname{ud}(S) \ge10p+2.

(⇒)(\Rightarrow) Suppose there exists an exact cover C∗⊆CC^{*} \subseteq C, so that ∣C∗∣=p|C^{*}|=p. In G1G_1, let S1=C∗∪{lj:Cj∈C∖C∗}S_1=C^{*}\cup\{l_j:C_j\in C\setminus C^{*}\}. In G2G_2, let S2S_2 consist of a single vertex. In G3G_3, let S3={r1,r1′}S_3=\{r_1,r'_1\}, a pair of non-adjacent vertices. Set S=S1∪S2∪S3S=S_1\cup S_2\cup S_3.

In G1G_1, every element of XX is adjacent to exactly one member of C∗C^{*} and to no leaf, hence is uni-dominated. Every Cj∈C∗C_j\in C^{*} is dominated by itself only, since lj∉S1l_j\notin S_1 and no element vertex belongs to S1S_1. Every Cj∉C∗C_j\notin C^{*} is dominated by ljl_j only. Every leaf ljl_j is dominated by CjC_j if Cj∈C∗C_j\in C^{*} and by itself otherwise. All 9p9p vertices of G1G_1 are therefore uni-dominated. In G2G_2, the chosen vertex is adjacent to all the others, so all pp vertices of G2G_2 are uni-dominated. In G3G_3, every vertex other than r1r_1 and r1′r'_1 is adjacent to both of them and is dominated twice, whereas r1r_1 and r1′r'_1 are dominated by themselves only. Hence V0(S)=∅V_0(S)=\varnothing and ud⁡(S)=9p+p+2=10p+2\operatorname{ud}(S)=9p+p+2=10p+2.

(⇐)(\Leftarrow) Suppose there exists a dominating set SS of GG with ud⁡(S)≥10p+2\operatorname{ud}(S)\ge10p+2, and let Si=S∩V(Gi)S_i=S\cap V(G_i). As GG is the disjoint union of G1G_1, G2G_2, and G3G_3, we have ud⁡(S)=ud⁡(S1)+ud⁡(S2)+ud⁡(S3)\operatorname{ud}(S)=\operatorname{ud}(S_1)+\operatorname{ud}(S_2)+\operatorname{ud}(S_3), each term being computed inside the corresponding part. Trivially ud⁡(S1)≤9p\operatorname{ud}(S_1)\le9p, and ud⁡(S2)≤p\operatorname{ud}(S_2)\le p because G2G_2 has pp vertices. In G3G_3 no vertex is universal, so ∣S3∣≥2|S_3|\ge2. If ∣S3∣=2|S_3|=2, then exactly two

vertices of G3G_3 are uni-dominated: the two chosen ones if they are non-adjacent, and their respective non-neighbors if they are adjacent. If ∣S3∣≥3|S_3| \ge3, then applying Lemma 12 inside G3G_3, where every vertex has exactly one non-neighbor, shows that no vertex of G3G_3 is uni-dominated. In both cases ud⁡(S3)≤2\operatorname{ud}(S_3) \le2.

The three upper bounds add up to 9p+p+2=10p+29p + p + 2 = 10p + 2, so each of them is attained. In particular every vertex of G1G_1 is uni-dominated.

Suppose that some element vertex x∈Xx \in X belongs to S1S_1. To ensure that xx is uni-dominated, none of its neighbors can belong to S1S_1. Let CjC_j be one of them. Since Cj∉S1C_j \notin S_1 and N[lj]={lj,Cj}N[l_j] = \{l_j,C_j\}, we must have lj∈S1l_j \in S_1. But then CjC_j is dominated by both xx and ljl_j, contradicting the fact that CjC_j is uni-dominated. Hence S1∩X=∅S_1 \cap X = \varnothing.

Consequently the elements of XX are dominated only by vertices of S1∩CS_1 \cap\mathcal{C}, and since all elements of XX are uni-dominated, the subsets of S1∩CS_1 \cap\mathcal{C} cover every element of XX exactly once. They form an exact cover of XX.

Proofs for Section 3 (The Non-Overlapping Uni-domination Problem)

Theorem 9 (⋆). Given a graph GG with nn vertices, the problem of deciding whether ud⁡+∗(G)≥4n\operatorname{ud}^{*}_{+}(G) \ge4\sqrt{n} is NP-complete, even for split graphs.

Proof. We use the notation of the reduction described in Section 3, and prove that the RX3C instance II has an exact cover if and only if GG admits a 2-packing SS such that ud⁡(S)≥4p\operatorname{ud}(S) \ge4p.

(⇒)(\Rightarrow) Suppose II has an exact cover consisting of exactly pp subsets Ci1,…,CipC_{i_1}, \ldots, C_{i_p}. Let SS consist of exactly one vertex from the gadget of each selected subset, which is possible since every gadget is non-empty, yielding ∣S∣=p|S| = p. Since the chosen subsets form an exact cover of XX, their neighborhoods in XX are pairwise disjoint. Because the chosen vertices also belong to independent sets, we have V+(S)=∅V_{+}(S) = \varnothing. Each of the pp vertices in SS dominates itself and exactly 3 vertices in XX. This yields

ud⁡(S)=∑v∈S(1+3)=4∣S∣=4p=4n,\operatorname{ud}(S) = \sum_{v \in S}(1+3) = 4|S| = 4p = 4\sqrt{n},

satisfying the threshold.

(⇐)(\Leftarrow) Conversely, assume there exists a set S⊆VS \subseteq V with V+(S)=∅V_{+}(S) = \varnothing and ud⁡(S)≥4p\operatorname{ud}(S) \ge4p. We analyze the intersection of SS with the clique XX:

  • Case 1: ∣S∩X∣≥2|S \cap X| \ge2. Since XX is a clique, two vertices of S∩XS \cap X are adjacent, so each of them is dominated twice, contradicting V+(S)=∅V_{+}(S) = \varnothing.

  • Case 2: ∣S∩X∣=1|S \cap X| = 1. Let S∩X={u}S \cap X = \{u\}. If SS contained a gadget vertex vv, then vv would dominate its 3 neighbors in XX. Since uu lies in the clique XX, it also dominates these 3 vertices. Those 3 vertices of XX are then over-dominated, forcing SS to be a singleton (S={u})(S = \{u\}). The vertex uu dominates itself, the remaining 3p−13p-1 vertices of XX, and the vertices of the three gadgets whose subsets contain uu. Let these subsets containing uu be CiC_i, CjC_j, and CkC_k. The number of uni-dominated vertices is bounded by ud⁡(S)≤1+(3p−1)+si+sj+sk=3p+si+sj+sk\operatorname{ud}(S) \le1 + (3p - 1) + s_i + s_j + s_k = 3p + s_i + s_j + s_k. We bound si+sj+sks_i + s_j + s_k separately in each congruence class:

  • If p≡0(mod3)p \equiv0 \pmod{3}, every gadget has size q−1=p3−1q-1=\frac{p}{3}-1, so ud⁡(S)≤3p+(p−3)=4p−3<4p\operatorname{ud}(S) \le3p+(p-3)=4p-3<4p.

  • If p≡1(mod3)p \equiv1 \pmod{3}, every gadget has size at most q=p−13q=\frac{p-1}{3}, so ud⁡(S)≤3p+(p−1)=4p−1<4p\operatorname{ud}(S) \le3p+(p-1)=4p-1<4p.

  • If p≡2(mod3)p \equiv2 \pmod{3}, every gadget has size at most q=p−23q=\frac{p-2}{3}, so ud⁡(S)≤3p+(p−2)=4p−2<4p\operatorname{ud}(S) \le3p+(p-2)=4p-2<4p.

In all cases, the configuration fails to reach the required threshold of 4p4p.

  • Case 3: ∣S∩X∣=0|S \cap X|=0. This forces SS to consist entirely of gadget vertices. There can be at most one vertex chosen from each gadget, otherwise, two vertices from the same gadget would share their three neighbors in XX, contradicting V+(S)=∅V_{+}(S)=\varnothing.

By assumption ud⁡(S)≥4n=4p\operatorname{ud}(S)\ge4\sqrt{n}=4p. Since each vertex in SS uni-dominates exactly four vertices (itself and three elements in XX), we must have 4∣S∣≥4p4|S|\ge4p, yielding ∣S∣≥p|S|\ge p.

Furthermore, to maintain V+(S)=∅V_{+}(S)=\varnothing, the corresponding subsets in XX must be pairwise disjoint. Since XX has 3p3p elements and each selected gadget covers three of them, we can select at most pp gadgets (3∣S∣≤3p3|S|\le3p).

Consequently, we must have exactly ∣S∣=p|S|=p. Because these pp disjoint subsets cover all 3p3p elements of XX, they constitute an exact cover for the RX3C instance.

Since only Case 3 meets the threshold, GG admits a 2-packing SS with ud⁡(S)≥4n\operatorname{ud}(S)\ge4\sqrt{n} if and only if the RX3C instance has a solution. □

Proofs for Section 4 (Comparison of the Two Variants)

Theorem 10 (⋆). For every even integer n≥4n\ge4, there exists a graph G=(V,E)G=(V,E) of order nn such that 2=ud⁡0∗(G)<ud⁡+∗(G)=n−12=\operatorname{ud}^{*}_{0}(G)<\operatorname{ud}^{*}_{+}(G)=n-1.

Proof. Let n≥4n\ge4 be an even integer and let GG be the complete graph on nn vertices minus a perfect matching, so that each vertex is adjacent to all the others except exactly one non-neighbor. This is precisely the graph constructed in the proof of Theorem 2 with c=2c=2 and p=(n−2)/2p=(n-2)/2: the independent set C={x1,x2}C=\{x_{1},x_{2}\} is the pair of ends of one non-edge, and the non-edges inside RR form the perfect matching of the remaining 2p2p vertices. Hence ud⁡0∗(G)=2\operatorname{ud}^{*}_{0}(G)=2 by Theorem 2. We now evaluate ud⁡+∗(G)\operatorname{ud}^{*}_{+}(G).

Let SS be a set with V+(S)=∅V_{+}(S)=\varnothing and suppose ∣S∣≥2|S|\ge2, say u,v∈Su,v\in S with u≠vu\ne v. If uv∈Euv\in E, then uu is dominated by both uu and vv, a contradiction. If uv∉Euv\notin E, then uu and vv are the two ends of a non-edge of the perfect matching, so the non-neighbor of any vertex w∉{u,v}w\notin\{u,v\} is neither uu nor vv. Since n≥4n\ge4 such a ww exists, and it is adjacent to both uu and vv, hence over-dominated, again a contradiction. Hence ∣S∣≤1|S|\le1.

For a singleton S={v}S=\{v\}, the vertex vv uni-dominates itself and all its n−2n-2 neighbors. No vertex is over-dominated, and only its non-neighbor remains undominated. This configuration directly yields ud⁡+∗(G)=n−1\operatorname{ud}^{*}_{+}(G)=n-1.

Hence, for every even integer n≥4n \ge4, we have 2=ud⁡0∗(G)<n−1=ud⁡+∗(G)2 = \operatorname{ud}^{*}_{0}(G) < n - 1 = \operatorname{ud}^{*}_{+}(G).

Theorem 11 (⋆). Every tree Tp∈TT_p \in\mathcal{T} has order n=p2+1n = p^2 + 1 and satisfies 3n−1−1=ud⁡+∗(Tp)<ud⁡0∗(Tp)=n−13\sqrt{n-1} - 1 = \operatorname{ud}^{*}_{+}(T_p) < \operatorname{ud}^{*}_{0}(T_p) = n - 1.

Proof. Let Tp∈TT_p \in\mathcal{T}, so that p≥3p \ge3. The construction is illustrated in Figure 5. The number of vertices is ∣V∣=n=1+p⋅(1+p−1)=p2+1|V| = n = 1 + p \cdot(1 + p - 1) = p^2 + 1, which implies p=n−1p = \sqrt{n-1}.

Figure 5. The structure of the tree TpT_p.

We first evaluate ud⁡+∗(Tp)\operatorname{ud}^{*}_{+}(T_p) by considering any subset S⊆VS \subseteq V satisfying V+(S)=∅V_{+}(S) = \varnothing, that is, any 2-packing SS.

Case 1: r∈Sr \in S.

The maximum distance from rr to any vertex in TpT_p is 2. Since any two distinct vertices in SS must be separated by a distance of at least 3, SS can contain no other vertices. Thus, S={r}S = \{r\}, yielding:

ud⁡(S)=∣N[r]∣=1+p\operatorname{ud}(S) = |N[r]| = 1 + p

Case 2: r∉Sr \notin S and S∩{r1,…,rp}≠∅S \cap\{r_1, \ldots, r_p\} \ne\varnothing.

Assume without loss of generality that r1∈Sr_1 \in S. Because d(r1,ri)=2d(r_1, r_i) = 2 for all i≠1i \ne1, SS cannot contain any other center rir_i. Thus, S∩{r1,…,rp}={r1}S \cap\{r_1, \ldots, r_p\} = \{r_1\}. The vertex r1r_1 dominates itself, the root rr, and its p−1p - 1 leaves, yielding a total of 1+1+(p−1)=p+11 + 1 + (p - 1) = p + 1 vertices.

Any other vertex in SS must be a leaf in some star AiA_i for i≠1i \ne1. In any star AiA_i, the distance between any two leaves is 2 (via rir_i). Hence SS contains at most one leaf from each AiA_i. Each chosen leaf dominates itself and its center rir_i, contributing exactly 2 vertices. Across the remaining p−1p - 1 stars, these leaves contribute at most 2(p−1)2(p - 1) vertices. In total, this case dominates at most:

ud⁡(S)≤(p+1)+2(p−1)=3p−1\operatorname{ud}(S) \le(p + 1) + 2(p - 1) = 3p - 1

Case 3: r∉Sr \notin S and S∩{r1,…,rp}=∅S \cap\{r_1,\ldots,r_p\} = \varnothing. All vertices in SS must be leaves. As established in Case 2, SS can contain at most one leaf per star. With pp stars available, SS contains at most pp leaves. Each leaf dominates two vertices (itself and its center). The total dominated vertices is bounded by:

ud⁡(S)≤2p\operatorname{ud}(S) \le2p

Comparing the three cases, and using p≥3p \ge3, we obtain, for every 2-packing SS,

ud⁡(S)≤max⁡{p+1, 3p−1, 2p}=3p−1.\operatorname{ud}(S) \le\max\{p+1,\,3p-1,\,2p\} = 3p-1.

This value is attained. Let S⋆S^{\star} consist of the center r1r_1 together with one leaf of AiA_i for each i≠1i \ne1. Then S⋆S^{\star} is a 2-packing: a leaf of AiA_i is at distance 3 from r1r_1, and two leaves belonging to two distinct stars are at distance 4. Since ud⁡(S)=∑v∈S(1+deg⁡(v))\operatorname{ud}(S) = \sum_{v \in S}(1+\deg(v)) for every 2-packing SS, we get ud⁡(S⋆)=(1+p)+2(p−1)=3p−1\operatorname{ud}(S^{\star}) = (1+p) + 2(p-1) = 3p-1, so ud⁡+⋆(Tp)=3p−1\operatorname{ud}_{+}^{\star}(T_p) = 3p-1.

We now evaluate ud⁡0⋆(Tp)\operatorname{ud}_{0}^{\star}(T_p). Consider the subset SS consisting of all center vertices, S={r1,r2,…,rp}S = \{r_1,r_2,\ldots,r_p\}. Each center rir_i dominates itself, its p−1p-1 leaves and the root rr.

Thus, every leaf is dominated exactly once (by its respective center rir_i). Every center rir_i is dominated exactly once (by itself, since the distance between any two distinct centers is 2, so they do not dominate each other). The root rr is adjacent to all pp centers, so it is dominated pp times.

Since p≥3p \ge3, the root rr is over-dominated (r∈V+(S)r \in V_{+}(S)). All other n−1n-1 vertices (leaves and centers) are uni-dominated, and V0(S)=∅V_{0}(S) = \varnothing.

This configuration yields ud⁡(S)=n−1\operatorname{ud}(S) = n-1, so ud⁡0⋆(Tp)≥n−1\operatorname{ud}_{0}^{\star}(T_p) \ge n-1.

Conversely, TpT_p has no dominating set uni-dominating all of its nn vertices, that is, no efficient dominating set. Indeed, let S′S' be such a set and consider a star AiA_i. If ri∉S′r_i \notin S', then every leaf of AiA_i must belong to S′S', since a leaf has rir_i as its only neighbor. As AiA_i has p−1≥2p-1 \ge2 leaves, the center rir_i would then be dominated at least twice, a contradiction. Hence ri∈S′r_i \in S' for every ii, and the root rr is dominated p≥3p \ge3 times, again a contradiction. Therefore ud⁡0⋆(Tp)=n−1\operatorname{ud}_{0}^{\star}(T_p) = n-1.

Comparing the two parameters for any p≥3p \ge3, we have ud⁡+⋆(Tp)=3p−1<p2=n−1=ud⁡0⋆(Tp)\operatorname{ud}_{+}^{\star}(T_p) = 3p-1 < p^2 = n-1 = \operatorname{ud}_{0}^{\star}(T_p), which completes the proof.

References

  1. [1]Bange, D.W., Barkauskas, A.E., Slater, P.J.: Efficient dominating sets in graphs. In: Ringeisen, R.D., Roberts, F.S. (eds.) Applications of Discrete Mathematics, pp. 189–199. SIAM, Philadelphia (1988)
  2. [2]Biggs, N.: Perfect codes in graphs. Journal of Combinatorial Theory, Series B 15(3), 289–296 (1973)DOI
  3. [3]Bollobás, B., Cockayne, E.J.J.: Graph-theoretic parameters concerning domination, independence, and irredundance. Journal of Graph Theory 3(3), 241–249 (1979)DOI
  4. [4]Cockayne, E.J., Hedetniemi, S.T., Miller, D.J.: Properties of hereditary hypergraphs and middle graphs. Canadian Mathematical Bulletin 21(4), 461–468 (1978)DOI
  5. [5]Goddard, W., Oellermann, O.R., Slater, P.J., Swart, H.C.: Bounds on the total redundance and efficiency of a graph. Ars Combinatoria 54, 129–138 (2000)
  6. [6]Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science 38, 293–306 (1985)DOI
  7. [7]Grinstead, D.L., Slater, P.J.: Fractional domination and fractional packing in graphs. Congressus Numerantium 71, 153–172 (1990)
  8. [8]Harary, F., Haynes, T.W., Slater, P.J.: Efficient and excess domination in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing 26, 83–95 (1998)
  9. [9]Haynes, T.W., Hedetniemi, S.T., Henning, M.A.: Domination in Graphs: Core Concepts. Springer (2023)DOI
  10. [10]Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
  11. [11]Hedetniemi, S.T., Rall, D.F.: On maximizing private neighbors in graphs. Communications in Combinatorics and Optimization 11(4), 1265–1279 (2026)arxiv.org/abs/2511.07248
  12. [12]Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics 61(1), 225–233 (1975)DOI
  13. [13]Milanič, M.: On the complexity of the efficient domination problem. Discrete Applied Mathematics 161(3), 413–420 (2013)
  14. [14]Ore, O.: Theory of graphs, American Mathematical Society Colloquium Publications, vol. 38. American Mathematical Society (1962)
  15. [15]Rubalcaba, R.R., Slater, P.J.: Efficient (j, k)-domination. Discussiones Mathematicae Graph Theory 27(3), 409–423 (2007)

Paper details

vlnc:W_px5njw5e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents