WorksComputer Science
Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
Abstract
A vertex is uni-dominated by a set if exactly one vertex of lies in its closed neighborhood, and the uni-domination number is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with . Hedetniemi and Rall asked for the largest constant with for every tree of order . We answer their question: the constant is , 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 under each of the two requirements separately, giving the Full-Cover variant and the Non-Overlapping variant . The two behave very differently: on arbitrarily large graphs may remain bounded by a constant, whereas 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 and , 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 of , is its open neighborhood and its closed neighborhood; is dominated by if , and 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 . A graph admitting such a set is called efficient. Such sets need not exist ( 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 , a vertex is an external private neighbor with respect to if and has exactly one neighbor in , and a self private neighbor if and . Hedetniemi and Rall [11] shifted the objective from the sets to the private neighbors they produce, defining seven maximization parameters based on different types of private neighbors. One of them, ESPN, maximizes the total number of external and self private neighbors over all , as is of one of these two types if and only if , 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 is uni-dominated by if , we write , , and , the uni-domination number of .
Thus , and is efficient if and only if . A set realizing 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 , and for the sets of vertices with 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 to be a dominating set, and the Non-Overlapping variant, requiring the closed neighborhoods of the vertices of to be pairwise disjoint, respectively,
Each relaxes efficient domination in one direction: of order is efficient if and only if , if and only if , and both are bounded above by the unrestricted parameter, . 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 of § 3.3.
Preliminaries
Throughout, is a finite simple undirected graph of order , for any vertex , and is the maximum degree of the vertices of . For , the subgraph induced by , denoted , has vertex set and contains exactly the edges of with both ends in . We write and . A vertex adjacent to all others is universal, a vertex with is a non-neighbor of , and is a -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 is irredundant if every has a private neighbor with respect to , that is, a vertex with , which is an external private neighbor if and a self private neighbor if . 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 is minimal if and only if, for every , the set leaves some vertex undominated. As is dominated by , this means exactly that , that is, is a private neighbor of . 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 with and a collection of 3-element subsets of in which every element of occurs in exactly three subsets. Question: Is there a subcollection that contains every element of 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 , the maximum number of vertices that can be dominated by a set dominating no vertex more than once, so that is efficient if and only if [1, 15]. In our notation , we keep the notation since our aim is to compare the two constrained variants of within one framework. Grinstead and Slater defined the influence of a set and observed that a set dominates no vertex more than once precisely when it is a -packing, whence [7, 15]. Goddard, Oellermann, Slater and Swart [5] proved the sharp bounds for every graph and for every tree, and deciding whether for an input is NP-complete [1, 5], whereas is computable in polynomial time on trees [1]. The companion of on the domination side is the redundance [7], which differs from : since , the quantity minimizes the total excess of domination, whereas 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 for paths, cycles and complete bipartite graphs. They also observed that for every tree and exhibited a family attaining , which led them to ask for the largest constant such that holds for every tree. We settle this question.
Our Results
Our main result is that every tree of order satisfies 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 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 for every graph of order (Theorem 1), and we exhibit, for every constant , arbitrarily large graphs with (Theorem 2). The case shows that the constant 2 cannot be improved. Deciding whether is polynomial for every fixed (Theorem 7), whereas the threshold makes the problem NP-complete for every fixed (Theorem 8).
For the Non-Overlapping parameter, [5] proved the sharp bound . 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 , 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 exceeds 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 are deferred to the appendix, except for the constructions of the two reductions.
Table 1. Summary of the results (entries with a reference are not proved here).
The Full-Cover Uni-domination Problem
Throughout this section is required to dominate every vertex, that is, , and the parameter is .
Structural Properties
Our first bound rests on the classical characterization of minimal dominating sets by private neighbors.
Theorem 1 (). Every graph with satisfies , and a dominating set with 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 , we show that under full coverage it can remain bounded by a constant.
Theorem 2 (⋆). For any integers and , there exists a graph of order with .
Proof (sketch). Given and , we construct as follows. Let the vertex set be partitioned into two disjoint subsets: and . We define the edge set such that there are no edges within , every vertex in is adjacent to every vertex in , and the induced subgraph on is a complete graph minus a perfect matching . Formally, . Clearly, . The construction is illustrated in Figure 1.

Figure 1. Construction of such that . Gray lines are edges and dashed lines are non-edges; the edges inside the shaded set are omitted.
The value is attained, for instance, by : every vertex of is dominated by all vertices of , while each vertex of the independent set is dominated by itself only, so that . Any set consisting of one vertex of and one vertex of is another optimal solution. For the upper bound, let be a dominating set. As has no universal vertex, . Every vertex of has exactly one non-neighbor, and is therefore dominated at least times. Hence, if , no vertex of is uni-dominated and . The dominating sets of size 2 are handled by a case analysis given in the appendix.
Trees
While Theorem 2 shows that 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 of order satisfies .
Proof. We proceed by induction on the order 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 are immediate. If , the tree is a path and its central vertex uni-dominates all three vertices. If , the tree is a path or a star, and in both cases it admits an efficient dominating set. Suppose now that . There are three non-isomorphic trees of order 5. If is a star, its center uni-dominates every vertex. If is a path, two vertices at distance 3 uni-dominate every vertex. It remains to consider the tree obtained from with center and leaves by subdividing the edge with a new vertex . The set is dominating and it uni-dominates , , and , while is dominated twice. Moreover, no subset of uni-dominates more than 4 vertices, so the bound is tight. In all these small cases .
Now let and assume that every tree of order less than satisfies the statement. Root at an arbitrary vertex and let be the height of the resulting rooted tree. If , then is a star and uni-dominates all vertices. If , let be the set of children of : every vertex is dominated, each child is uni-dominated by itself since two children of are never adjacent and no grandchild belongs to , and each grandchild is uni-dominated by its parent. Only may be dominated more than once, so since . We may therefore assume . Let be a vertex of maximum depth. Since , it has a parent , a grandparent and a great-grandparent . By maximality of the depth, is a leaf, every child of is a leaf, and every child of is either a leaf or a vertex all of whose children are leaves. Let be the subtree rooted at and put . The only edge joining to the rest of is . Consequently is again a tree, of order since it contains . We distinguish three cases according to .
Case 1: (panel A of Figure 2). Let be the children of , with . By the choice of , every child of every is a leaf. By the induction hypothesis, has a dominating set with . Put and . Each is uni-dominated by itself, since and none of its children belongs to . Each child of is a leaf uni-dominated by . The vertex , being adjacent to all the vertices of , is dominated but possibly more than once, so we do not count it. Hence dominates and uni-dominates at least of its vertices. The two parts do not interfere: every vertex of has all its neighbors inside , so dominates no vertex of , and conversely is the only vertex of with a neighbor outside . Therefore is a dominating set of and, using , we obtain .
Case 2: (panels B1–B4 of Figure 2). Exactly two configurations are possible: either has a single child and has exactly two leaf children , or has exactly two children, namely with a single leaf child , and a leaf . Here we remove as well: let , so . Since is removed, the forest may be disconnected. Let be its components. Each is a tree of order less than , so the induction hypothesis provides a dominating set of with . Put . As no edge joins two components, dominates and uni-dominates at least of its vertices. We choose according to whether is dominated by its neighbors in , that is, whether has a neighbor in , and set . Since and , we have .
Suppose first that is dominated by its neighbors in , as in panels B1 and B2. The vertex is then dominated, possibly several times, and we do not count it among the uni-dominated vertices. The four vertices of , on the other hand, are all uni-dominated. In panel B1 we take : the vertex is uni-dominated by itself, since none of lies in , and and are uni-dominated by , the only other neighbor of being . In panel B2 we take : the vertices and are uni-dominated by themselves, is uni-dominated by , and by , again because .
Suppose now that is not dominated by its neighbors in , as in panels B3 and B4. We then put in , so that is uni-dominated by itself, since and , and is uni-dominated by , its only neighbor in . In panel B3 we take : and are uni-dominated by themselves since , only is over-dominated, being adjacent to the three vertices of . In panel B4 we take : the vertex is uni-dominated by itself, is uni-dominated by , only is over-dominated, being adjacent to both and .
In each of the four configurations every vertex of is dominated and at least four of these five vertices are uni-dominated. Moreover every vertex of has all its neighbors in , so dominates no vertex of . Conversely is the only vertex outside with a neighbor in , and is counted only in panels B3 and B4, where it has no neighbor in . Hence is a dominating set of and .
Case 3: . Here has a single child , which in turn has a single leaf child . By the induction hypothesis, the tree , of order , has a dominating set with . This time the choice of depends on whether belongs to , the two resulting configurations being drawn in panels C1 and C2 of Figure 2. If , take : then is uni-dominated by itself, by since , and by since . If , take : then uni-dominates , itself and , the latter because the only other neighbor of is . In both cases the three vertices of are uni-dominated, and since and , the set dominates no vertex of . Hence is a dominating set of and .
In all cases we have exhibited a dominating set of with , 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 . Moreover, the tree considered in the proof of Theorem 3 shows that the constant cannot be improved, even without the domination requirement.
Corollary 4. Every tree of order satisfies . Moreover, the constant is best possible for both parameters.
Proof. The inequalities follow from Theorem 3 and . For sharpness, consider the tree 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 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 (). For every tree of order , a dominating set of with can be computed in 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 and a positive integer . |
| Question: Is ? |
Table 1 (PDF p. 8).
The complexity of FCUD depends on the threshold . For a constant , the dominators of uni-dominated vertices form a core of at most vertices, and adding every vertex outside keeps uni-dominated. It then suffices to test whether this expanded set dominates , as formalized in Lemma 6.
Lemma 6 (). Let be a graph and be an integer. For any subset , let be the set of vertices that are neither in nor adjacent to a vertex of . There exists a dominating set such that if and only if there exist a target subset with and a core subset with satisfying the following conditions:
.
The expanded set is a dominating set of .
Because this lemma reduces the search space to subsets of size bounded by , we obtain a polynomial-time algorithm.
Theorem 7 (). For any fixed integer , given a graph , the problem of deciding whether is solvable in polynomial time.
In contrast, when the threshold grows with the order of the graph, the problem becomes NP-complete.
Theorem 8 (). For any fixed integer , given a graph , the problem of deciding whether (where ) is NP-complete.
Proof (sketch). The problem is in NP, as for a given subset one can check in polynomial time whether and . To prove NP-hardness, we perform a polynomial-time reduction from RX3C. The reduction is described below.
Let be an instance of RX3C, so that , and set . We construct as the disjoint union of three graphs , and . The part encodes the instance , adds vertices so that is even, which makes the order of even, and is a padding part whose contribution to the uni-domination is a controlled constant and whose size brings the order of to a -th power.
Part : We create three layers of vertices. The bottom layer consists of vertices representing the elements . The middle layer consists of vertices representing the subsets . We add an edge between a
vertex representing an element and a vertex representing a subset if and only if . Finally, the top layer consists of pendant vertices , the leaf being adjacent to the subset vertex only. Thus .
Part : We construct a complete graph on exactly vertices. Thus .
Part : Let . Since is even, is even, and as is even, is an even integer. Moreover , so . We let be a complete graph on vertices minus a perfect matching, that is, where , all pairs of vertices being adjacent except the pairs .
The construction is illustrated in Figure 3. The total number of vertices of is , so the required threshold is . Since is fixed and the numbers of vertices and edges of are bounded by a polynomial in , this instance is constructed in polynomial time in the size of . It remains to prove that has an exact cover if and only if admits a dominating set with (see the appendix).

Figure 3. The construction of graph , the disjoint union of , and . Gray lines are edges and dashed lines are non-edges; the edges of are omitted.
The Non-Overlapping Uni-domination Problem
Throughout this section . Every vertex it dominates is then dominated exactly once, so .
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 for every graph of order , and exhibited graphs of diameter 2 obtained from projective planes for which .
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, and , uses only that the 2-packing under consideration contains a vertex of maximum degree and is maximal, respectively: a maximal 2-packing satisfies , 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 with and, as long as some vertex is at distance at least 3 from every vertex of , adding such a vertex to . As the first bound is increasing and the second one is decreasing in , and the two coincide at , their maximum is at least for every . Hence such a set already satisfies , so the bound of [5] is attained constructively.
No lower bound linear in holds, even on trees: the same authors proved the sharp bound for every tree of order , together with an extremal family attaining it [5]. The contrast with Theorem 3, which guarantees 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 and a positive integer . |
| Question: Is ? |
Table 1 (PDF p. 11).
For a fixed constant threshold , the answer is positive whenever , by the bound 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 to , already makes the problem NP-complete on split graphs.
Theorem 9 (⋆). Given a graph with vertices, the problem of deciding whether is NP-complete, even for split graphs.
Proof (sketch). The problem is in NP, as verifying whether a given subset satisfies and can be done in polynomial time. To prove NP-hardness, we present a polynomial-time reduction from the RX3C problem. Let be an instance of RX3C, with and . Instances with have bounded size and are solved in constant time, so we may assume .
We construct as follows. Each element of becomes a vertex, and is turned into a clique of size . Each subset receives a gadget consisting of an independent set of vertices, each of them joined to the three vertices of corresponding to the elements of . Since is partitioned into the clique and the independent set of all gadget vertices, is a split graph.
The construction is illustrated in Figure 4, and the sizes are chosen so that the order of equals . Let , and note that because , so every gadget receives at least one vertex. If , set for all gadgets, so that . If , set for exactly gadgets and for the other , so that . If , set for exactly gadgets and for the other , so that . In all three cases , so and the required threshold is . So has vertices and edges, hence is built in polynomial time. It remains to prove that has an exact cover if and only if admits a 2-packing with (see the appendix).

Figure 4. The graph built from an RX3C instance in the proof of Theorem 9. The shaded rectangle is the clique , 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 minus a perfect matching, on which exceeds by a factor of order .
Theorem 10 (⋆). For every even integer , there exists a graph of order such that .
The second family consists of trees. For an integer , we construct a tree as follows: create a root vertex ; create star graphs , where each star consists of a center vertex and leaves; add an edge between the root and each center . We set . The restriction is necessary: the same construction with produces the path , which admits an efficient dominating set, so that both parameters equal 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 .
Theorem 11 (⋆). Every tree has order and satisfies .
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 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 , and this is sharp, yet deciding whether is NP-complete, so that the complexity of the intermediate thresholds with 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 (). Every graph with satisfies , and a dominating set with can be constructed in polynomial time.
Proof. We first observe that every minimal dominating set of satisfies . Indeed, a dominating set is minimal if and only if it is irredundant [4, 9], so every has a private neighbor with respect to , that is, a vertex with . In particular . If for two distinct , then , a contradiction, so the mapping is injective and .
Now assume . A minimal dominating set is obtained in polynomial time by a standard greedy reduction: initialize and remove a vertex from whenever still dominates . One pass over the vertices suffices, and the resulting set is a minimal dominating set, so by the observation above. If , we obtain . If , say , then dominates on its own and is therefore a universal vertex, so and . In both cases the polynomially constructed dominating set is a witness for . □
Lemma 12. Let be a graph and let have exactly non-neighbors in . For any subset with , the vertex is not uni-dominated by .
Proof. Write for the set of the non-neighbors of , so that . Since is the disjoint union of and , the number of times is dominated by equals . Hence and is not uni-dominated. □
Theorem 2 (). For any integers and , there exists a graph of order with .
Proof. Let be the graph constructed in the main text and illustrated in Figure 1, its order is . By construction, there are no edges between any two vertices in , making an independent set of size . Every vertex in is non-adjacent only to the other vertices within . Meanwhile, every vertex in is connected to all vertices in and all vertices in except its unique non-neighbor. Thus, every vertex in has exactly one non-neighbor in .
Let be a dominating set of . Since has no universal vertex, we must have . We evaluate based on the cardinality of :
Case 1: . For any vertex , its number of non-neighbors is exactly one. By Lemma 12 applied with , since , no vertex in can be uni-dominated. Consequently, . Since , it follows that .
Case 2: . Let . We analyze the possible configurations of :
If : since is an independent set, neither nor dominates the other, and no vertex of is adjacent to either of them. Two sub-cases arise. If , then any satisfies , so is not a dominating set and this configuration does not occur. If , then : every vertex of is adjacent to both and , hence is dominated twice, while and are each dominated by themselves only. Consequently and .
If and : Since and are adjacent, they dominate each other, meaning . For the remaining vertices, any vertex in is adjacent to but not , so it is dominated exactly once. For vertices in , they are all adjacent to . They are also adjacent to , except for the unique non-neighbor of . Thus, is only dominated by , so . This yields , giving exactly .
If : First, since every vertex in is adjacent to all vertices in , covers . Second, within , every vertex has exactly one non-neighbor. Since contains two distinct vertices and , the only vertex not dominated by is its unique non-neighbor, which is necessarily dominated by , and vice versa. Thus, the entire graph is dominated (). Furthermore, because both and are adjacent to all of , every vertex in is dominated exactly twice, meaning . Since the non-edges of form the perfect matching , will contain exactly two vertices (either and if , or their respective unique non-neighbors if ). Thus, .
Therefore, for any dominating set of size 2, we have .
From both cases, we establish that for any dominating set . This upper bound is achievable through two distinct structural configurations. As shown in Case 2, any dominating set consisting of exactly one vertex of and one vertex of yields exactly . The second one is , already met in Case 2 for and available for every : since , every vertex of is adjacent to all vertices of , so , and since is an independent set, each vertex of is dominated by itself only. No vertex is left undominated () and , which again yields . Having established both the upper bound and its attainability, we conclude that .
Corollary 5 (⋆). For every tree of order , a dominating set of with can be computed in 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 at an arbitrary vertex . One traversal computes, for every vertex, its parent, its list of children and its depth, and groups the vertices into buckets 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 containing , 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 , and the height of the active tree is the largest depth of an active vertex.
One step. Let be an active vertex of maximum depth. If at most 5 vertices are active, or if , the active tree is terminal and is treated as described below. Otherwise has a parent , a grandparent and a great-grandparent , all active. We let be the active subtree rooted at and . Deleted vertices are grouped into bags: some bags are determined at once, the others store a rule depending on the membership in of a single active vertex, to which the bag is then attached. The three cases of Theorem 3 are handled as follows.
Case . The bag is and the choice , where are the active children of , is fixed immediately. By Case 1 of Theorem 3 every vertex of the bag is dominated, at least of them are uni-dominated, and no vertex of has a neighbor outside the bag.
Case . The bag is , it is attached to and stores the rule of Case 3 of Theorem 3, namely if and if . Under both alternatives , so no vertex of the bag dominates , and all three vertices of the bag are uni-dominated.
Case . Here has order 5, and we delete the whole active subtree rooted at , that is, together with the subtrees rooted at the active children of other than , we call the latter the side components. Since has maximum depth, every active vertex has depth at most , so a side component, whose root has depth , 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 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 uni-dominated vertices for a component of order . As the only neighbor of a side component outside it is , and never belongs to the set chosen inside , these components require no later decision.
Scanning the roots of the side components tells us whether already has a selected neighbor below it. If it does, the corresponding choice of Case 2 of Theorem 3 for a vertex having a neighbor in is fixed at once. Otherwise the only neighbor of outside whose status is still undecided is its parent , and the bag is attached to : the first choice if , the second one if . If there is no such ; the second choice is fixed at once, and the deletion of the subtree rooted at empties the active tree, so that only the propagation phase remains. In all cases , so the bag does not dominate . Every vertex of 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 and in the induction step of Theorem 3. In both situations the active tree is dominated, at least 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 becomes known, every bag attached to 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 . A bag of the case contributes at least uni-dominated vertices out of , a bag of the case at least 4 out of 5, a bag of the case exactly 3 out of 3, and each side component as well as the terminal component at least a fraction of its vertices. Summing gives , provided that no choice destroys the domination counted in another part. This is the content of Theorem 3, transposed as follows. In the case the only vertex of the bag with a neighbor outside it is , which is not counted, and no vertex of has a neighbor outside the bag. In the case the only outside neighbor is , and the rule stored in the bag distinguishes the two possible statuses of . In the case the only vertex of with neighbors outside is , and the rule again distinguishes the two possible statuses of the outside neighbors of .
It remains to check that postponing the decision of a bag creates no conflict. Let be a bag attached to a vertex . Whichever of its two alternatives is eventually chosen, the vertex of adjacent to , namely in the case and in the case , is not selected. Hence contributes no selected neighbor to , so the domination status of , and of every vertex that is still active, does not depend on , and the active tree can be processed as if had been removed. Conversely, when is created, is the only vertex with a neighbor in whose membership in is still undecided, and the rule stored in prescribes a correct choice both for and for . Therefore, once all bags are resolved, every vertex of is dominated, and every vertex counted in a bag is uni-dominated by the final set .
Running time. The initialization takes time. To find an active vertex of maximum depth we scan the buckets 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 in total. When is processed, its children and grandchildren are scanned in order to build , and is then deleted. In the case the children of are scanned once and 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 , the total running time is , and the algorithm uses space.
Lemma 6 (⋆). Let be a graph and be an integer. For any subset , let be the set of vertices that are neither in nor adjacent to a vertex of . There exists a dominating set such that if and only if there exist a target subset with and a core subset with satisfying the following conditions:
.
The expanded set is a dominating set of .
Proof. (⇒) Assume there exists a dominating set of with . We can choose a target subset of exactly uni-dominated vertices. Let . By definition, , which allows us to distribute the intersection: . Because each is uni-dominated by , the intersection contains exactly one vertex. Since , this unique dominator belongs to , which is exactly . Thus, dominates . Furthermore, because and uni-dominates , cannot dominate more than once. Therefore, uni-dominates , yielding . Additionally, since is the union of exactly singleton sets, its cardinality is bounded by .
Next, we show that the expanded set is a dominating set of . Consider an arbitrary vertex . We distinguish two cases:
Case 1: . By the construction of , is directly included in , meaning it is dominated by itself.
Case 2: . Since the original set is a dominating set of , must be dominated by some vertex . We consider where lies:
Subcase 2.1: . Because and , belongs to their intersection. By our earlier definition , which directly implies . Since , the vertex is present in .
Subcase 2.2: . By the definition of the remaining set , any vertex not in must belong to . Thus, . Since , the vertex is again present in .
In all scenarios, the vertex responsible for dominating is guaranteed to be in , proving that is indeed a dominating set.
(⇐) Assume such subsets and exist. By condition 2, is a dominating set of . Consider an arbitrary vertex . Since , we have , and therefore is disjoint from . Therefore, the intersection of its closed neighborhood with the expanded set simplifies to . By condition 1, is uni-dominated by , meaning . This implies . Because this unique domination property holds for every single vertex , every such vertex is uni-dominated by . Consequently, the entire target set is contained in . Given that , we conclude that .
Theorem 7 (⋆). For any fixed integer , given a graph , the problem of deciding whether is solvable in polynomial time.
Proof. Given a graph with and a fixed integer , we algorithmically verify if by applying the expansion logic from Lemma 6:
Generate all possible target subsets of size exactly one by one.
Generate all possible core subsets of size at most one by one.
For each pair , check if uni-dominates . If it does, expand into (where ). Check if this expanded set dominates the entire graph .
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 is fixed, the number of target subsets generated in Step 1 is . Similarly, the number of core subsets generated in Step 2 is bounded by , which is also . The algorithm therefore evaluates at most pairs of . Inside the loop, for each pair, isolating the non-adjacent set , verifying the local uni-domination on , and confirming the global domination of can all be executed in time. The overall worst-case time complexity is bounded by . This running time is polynomial, which concludes the proof.
Theorem 8 (⋆). For any fixed integer , given a graph , the problem of deciding whether (where ) is -complete.
Proof. We use the notation of the reduction described in § 2.3, and prove that the RX3C instance has an exact cover if and only if admits a dominating set with .
Suppose there exists an exact cover , so that . In , let . In , let consist of a single vertex. In , let , a pair of non-adjacent vertices. Set .
In , every element of is adjacent to exactly one member of and to no leaf, hence is uni-dominated. Every is dominated by itself only, since and no element vertex belongs to . Every is dominated by only. Every leaf is dominated by if and by itself otherwise. All vertices of are therefore uni-dominated. In , the chosen vertex is adjacent to all the others, so all vertices of are uni-dominated. In , every vertex other than and is adjacent to both of them and is dominated twice, whereas and are dominated by themselves only. Hence and .
Suppose there exists a dominating set of with , and let . As is the disjoint union of , , and , we have , each term being computed inside the corresponding part. Trivially , and because has vertices. In no vertex is universal, so . If , then exactly two
vertices of are uni-dominated: the two chosen ones if they are non-adjacent, and their respective non-neighbors if they are adjacent. If , then applying Lemma 12 inside , where every vertex has exactly one non-neighbor, shows that no vertex of is uni-dominated. In both cases .
The three upper bounds add up to , so each of them is attained. In particular every vertex of is uni-dominated.
Suppose that some element vertex belongs to . To ensure that is uni-dominated, none of its neighbors can belong to . Let be one of them. Since and , we must have . But then is dominated by both and , contradicting the fact that is uni-dominated. Hence .
Consequently the elements of are dominated only by vertices of , and since all elements of are uni-dominated, the subsets of cover every element of exactly once. They form an exact cover of .
Proofs for Section 3 (The Non-Overlapping Uni-domination Problem)
Theorem 9 (⋆). Given a graph with vertices, the problem of deciding whether 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 has an exact cover if and only if admits a 2-packing such that .
Suppose has an exact cover consisting of exactly subsets . Let consist of exactly one vertex from the gadget of each selected subset, which is possible since every gadget is non-empty, yielding . Since the chosen subsets form an exact cover of , their neighborhoods in are pairwise disjoint. Because the chosen vertices also belong to independent sets, we have . Each of the vertices in dominates itself and exactly 3 vertices in . This yields
satisfying the threshold.
Conversely, assume there exists a set with and . We analyze the intersection of with the clique :
Case 1: . Since is a clique, two vertices of are adjacent, so each of them is dominated twice, contradicting .
Case 2: . Let . If contained a gadget vertex , then would dominate its 3 neighbors in . Since lies in the clique , it also dominates these 3 vertices. Those 3 vertices of are then over-dominated, forcing to be a singleton . The vertex dominates itself, the remaining vertices of , and the vertices of the three gadgets whose subsets contain . Let these subsets containing be , , and . The number of uni-dominated vertices is bounded by . We bound separately in each congruence class:
If , every gadget has size , so .
If , every gadget has size at most , so .
If , every gadget has size at most , so .
In all cases, the configuration fails to reach the required threshold of .
Case 3: . This forces 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 , contradicting .
By assumption . Since each vertex in uni-dominates exactly four vertices (itself and three elements in ), we must have , yielding .
Furthermore, to maintain , the corresponding subsets in must be pairwise disjoint. Since has elements and each selected gadget covers three of them, we can select at most gadgets ().
Consequently, we must have exactly . Because these disjoint subsets cover all elements of , they constitute an exact cover for the RX3C instance.
Since only Case 3 meets the threshold, admits a 2-packing with 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 , there exists a graph of order such that .
Proof. Let be an even integer and let be the complete graph on 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 and : the independent set is the pair of ends of one non-edge, and the non-edges inside form the perfect matching of the remaining vertices. Hence by Theorem 2. We now evaluate .
Let be a set with and suppose , say with . If , then is dominated by both and , a contradiction. If , then and are the two ends of a non-edge of the perfect matching, so the non-neighbor of any vertex is neither nor . Since such a exists, and it is adjacent to both and , hence over-dominated, again a contradiction. Hence .
For a singleton , the vertex uni-dominates itself and all its neighbors. No vertex is over-dominated, and only its non-neighbor remains undominated. This configuration directly yields .
Hence, for every even integer , we have .
Theorem 11 (⋆). Every tree has order and satisfies .
Proof. Let , so that . The construction is illustrated in Figure 5. The number of vertices is , which implies .
Figure 5. The structure of the tree .
We first evaluate by considering any subset satisfying , that is, any 2-packing .
Case 1: .
The maximum distance from to any vertex in is 2. Since any two distinct vertices in must be separated by a distance of at least 3, can contain no other vertices. Thus, , yielding:
Case 2: and .
Assume without loss of generality that . Because for all , cannot contain any other center . Thus, . The vertex dominates itself, the root , and its leaves, yielding a total of vertices.
Any other vertex in must be a leaf in some star for . In any star , the distance between any two leaves is 2 (via ). Hence contains at most one leaf from each . Each chosen leaf dominates itself and its center , contributing exactly 2 vertices. Across the remaining stars, these leaves contribute at most vertices. In total, this case dominates at most:
Case 3: and . All vertices in must be leaves. As established in Case 2, can contain at most one leaf per star. With stars available, contains at most leaves. Each leaf dominates two vertices (itself and its center). The total dominated vertices is bounded by:
Comparing the three cases, and using , we obtain, for every 2-packing ,
This value is attained. Let consist of the center together with one leaf of for each . Then is a 2-packing: a leaf of is at distance 3 from , and two leaves belonging to two distinct stars are at distance 4. Since for every 2-packing , we get , so .
We now evaluate . Consider the subset consisting of all center vertices, . Each center dominates itself, its leaves and the root .
Thus, every leaf is dominated exactly once (by its respective center ). Every center 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 is adjacent to all centers, so it is dominated times.
Since , the root is over-dominated (). All other vertices (leaves and centers) are uni-dominated, and .
This configuration yields , so .
Conversely, has no dominating set uni-dominating all of its vertices, that is, no efficient dominating set. Indeed, let be such a set and consider a star . If , then every leaf of must belong to , since a leaf has as its only neighbor. As has leaves, the center would then be dominated at least twice, a contradiction. Hence for every , and the root is dominated times, again a contradiction. Therefore .
Comparing the two parameters for any , we have , which completes the proof.
References
- [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]Biggs, N.: Perfect codes in graphs. Journal of Combinatorial Theory, Series B 15(3), 289–296 (1973)DOI
- [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]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]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]Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science 38, 293–306 (1985)DOI
- [7]Grinstead, D.L., Slater, P.J.: Fractional domination and fractional packing in graphs. Congressus Numerantium 71, 153–172 (1990)
- [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]Haynes, T.W., Hedetniemi, S.T., Henning, M.A.: Domination in Graphs: Core Concepts. Springer (2023)DOI
- [10]Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
- [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]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]Milanič, M.: On the complexity of the efficient domination problem. Discrete Applied Mathematics 161(3), 413–420 (2013)
- [14]Ore, O.: Theory of graphs, American Mathematical Society Colloquium Publications, vol. 38. American Mathematical Society (1962)
- [15]Rubalcaba, R.R., Slater, P.J.: Efficient (j, k)-domination. Discussiones Mathematicae Graph Theory 27(3), 409–423 (2007)

