Efficient dominating set

In graph theory, an efficient dominating set (also called an e.d. set or independent perfect dominating set^[1]) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set.^[2]

The two darker vertices at the top form an efficient dominating set of the graph. Each vertex of the graph is dominated by exactly one vertex in this set (colored by which one dominates it), including the vertices of the set, each of which dominates itself.

The efficient domination problem (ED problem) asks whether a given graph contains an efficient dominating set. The problem is NP-complete for general graphs^[2] and remains NP-complete even when restricted to 3-regular planar graphs.^[3]

Definition

A vertex ${\displaystyle v}$ in a graph dominates itself and all its neighbors, that is, every vertex ${\displaystyle u}$ such that ${\displaystyle u=v}$ or ${\displaystyle uv\in E}$. A dominating set ${\displaystyle D}$ is a set of vertices such that every vertex in the graph is dominated by at least one vertex in ${\displaystyle D}$. An efficient dominating set strengthens this condition by requiring that every vertex is dominated by exactly one vertex in ${\displaystyle D}$.^[2]

More formally, a vertex set ${\displaystyle D\subseteq V}$ in a graph ${\displaystyle G=(V,E)}$ is an efficient dominating set if for every vertex ${\displaystyle v\in V}$, there is exactly one ${\displaystyle d\in D}$ such that ${\displaystyle v}$ is in the closed neighborhood ${\displaystyle N_{G}[d]}$ of ${\displaystyle d}$.^[2]

An equivalent characterization is that the closed neighborhoods ${\displaystyle {N_{G}[d]:d\in D}}$ form a partition of the vertex set ${\displaystyle V}$.^[3]

Every efficient dominating set is necessarily a minimum dominating set, since the closed neighborhoods partition the vertex set.^[3] However, not every minimum dominating set is efficient.

Complexity

The efficient domination problem is NP-complete for several graph classes, including bipartite graphs, chordal graphs, and chordal bipartite graphs^[2]. The problem remains NP-complete even when restricted to 3-regular planar graphs.^[3]

However, the problem can be solved in polynomial time for certain restricted graph classes:^[2][3]

• Dually chordal graphs can be solved in linear time
• AT-free graphs can be solved in polynomial time
• Interval bigraphs can be solved in polynomial time
• Trees can be solved in linear time

Examples

Sierpiński graphs ${\displaystyle S(n,k)}$ provide notable examples of graphs with efficient dominating sets. These graphs possess essentially unique efficient dominating sets for all parameters ${\displaystyle n}$ and ${\displaystyle k}$.^[4][5]

The closely related Sierpiński gasket graphs ${\displaystyle S_{n}}$, which arise from iterations leading to the Sierpiński gasket, have a much more restrictive structure: they contain an efficient dominating set if and only if ${\displaystyle n=1}$ or ${\displaystyle n=3}$.^[5]

Circulant graphs provide another well-studied class for efficient dominating sets. A circulant graph ${\displaystyle {\text{Cay}}(\mathbb {Z} _{n},S)}$ is a Cayley graph on the cyclic group ${\displaystyle \mathbb {Z} _{n}}$ with connection set ${\displaystyle S}$, where ${\displaystyle S=-S}$ and ${\displaystyle 0\notin S}$. Such a graph has vertices ${\displaystyle \{0,1,\ldots ,n-1\}}$ with edges connecting vertices whose difference lies in ${\displaystyle S}$.^[6]

For a circulant graph ${\displaystyle {\text{Cay}}(\mathbb {Z} _{n},S)}$ to admit an efficient dominating set ${\displaystyle D}$, a necessary condition is ${\displaystyle n=|S_{0}|\cdot |D|}$, where ${\displaystyle S_{0}=S\cup \{0\}}$.^[6]

For connected non-complete circulant graphs of degree ${\displaystyle |S|=p-1}$ where ${\displaystyle p}$ is prime, an efficient dominating set exists if and only if ${\displaystyle s-s'\not \equiv 0{\pmod {p}}}$ for any distinct ${\displaystyle s,s'\in S_{0}}$. When this condition holds, all efficient dominating sets are precisely the cosets ${\displaystyle g+p\mathbb {Z} _{n}}$ for ${\displaystyle g\in \mathbb {Z} _{n}}$.^[6]

Similar characterizations exist for circulant graphs of degree ${\displaystyle |S|=pq-1}$ and ${\displaystyle |S|=p^{m}-1}$, where ${\displaystyle p,q}$ are primes and ${\displaystyle m}$ is a positive integer, provided that ${\displaystyle |S|+1}$ is relatively prime to ${\displaystyle {\frac {n}{|S|+1}}}$.^[6]

History and applications

The concept of efficient dominating sets was introduced independently by two groups of researchers. Norman Biggs first studied these structures in 1973 under the name perfect codes in the context of coding theory and distance-transitive graphs.^[7] Later, apparently unaware of Biggs's work, Bange, Barkauskas, and Slater independently defined the concept as efficient dominating sets and developed linear time algorithms for finding them in trees.^[1][3]

Efficient dominating sets have applications in resource allocation problems for parallel computing. When modeling a parallel computer's processors and interconnection network as a graph, an efficient dominating set represents an optimal placement of limited resources (such as disk drives, I/O connections, or software modules) such that every processor is within distance ${\displaystyle d}$ of exactly one resource unit, with neither duplication nor overlap.^[3]

The concept has been extended to fuzzy graphs and intuitionistic fuzzy graphs, where efficient domination has been applied to encryption and decryption problems. In these applications, efficient dominating nodes serve as centers of subnetworks in the encryption scheme, and identifying the efficiently dominating set becomes the secret key for decryption.^[8]

For hypercube graphs, a distance d efficient dominating set corresponds precisely to a perfect binary d-error-correcting code.^[3][7] This connection links the graph-theoretic concept to coding theory.

Related problems

The efficient edge domination problem (EED problem) is the edge-analogue of the efficient domination problem. An efficient edge dominating set ${\displaystyle M\subseteq E}$ is a set of edges such that every edge ${\displaystyle e\in E}$ is intersected by exactly one edge ${\displaystyle e'\in M}$. The EED problem can be solved in linear time for chordal graphs and dually chordal graphs.^[2]

A strong efficient dominating set is a variant where domination is restricted to neighbors of equal or higher degree. Formally, a set ${\displaystyle S\subseteq V}$ is a strong efficient dominating set if for every ${\displaystyle v\in V}$, there is exactly one vertex in ${\displaystyle S}$ that either equals ${\displaystyle v}$ or is adjacent to ${\displaystyle v}$ with degree at least ${\displaystyle \deg(v)}$. Unlike standard efficient dominating sets, which all have the same cardinality in a given graph, strong efficient dominating sets of the same graph may have different cardinalities.^[9]

The concept extends naturally to distance d perfect dominating sets (or distance d PDS). A vertex ${\displaystyle v}$ d-dominates a vertex ${\displaystyle u}$ if the distance between them is at most ${\displaystyle d}$. A set ${\displaystyle D}$ is a distance d perfect dominating set if every vertex in the graph is d-dominated by exactly one vertex in ${\displaystyle D}$.^[3]

The concept also extends to hypergraphs, where similar complexity results have been established.^[2]