Efficient dominating set

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

by exactly one vertex in this set (colored by which one dominates it), including the vertices of the set, each of which dominates itself. In graph theory, an efficient dominating set (also called an e.d. set or independent perfect dominating set ) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set. The efficient domination problem (ED problem) asks whether a given graph contains an efficient dominating set. The problem is NP-complete for general graphs and remains NP-complete even when restricted to 3-regular planar graphs.

by exactly one vertex in this set (colored by which one dominates it), including the vertices of the set, each of which dominates itself. In graph theory, an efficient dominating set (also called an e.d. set or independent perfect dominating set ) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set. The efficient domination problem (ED problem) asks whether a given graph contains an efficient dominating set. The problem is NP-complete for general graphs and remains NP-complete even when restricted to 3-regular planar graphs. A vertex v in a graph dominates itself and all its neighbors, that is, every vertex u such that u = v or uv \in E . A dominating set D is a set of vertices such that every vertex in the graph is dominated by at least one vertex in D . An efficient dominating set strengthens this condition by requiring that every vertex is dominated by exactly one vertex in D . More formally, a vertex set D \subseteq V in a graph G = (V,E) is an efficient dominating set if for every vertex v \in V , there is exactly one d \in D such that v is in the closed neighborhood N_G[d] of d . An equivalent characterization is that the closed neighborhoods {N_G[d] : d \in D} form a partition of the vertex set V . Every efficient dominating set is necessarily a minimum dominating set, since the closed neighborhoods partition the vertex set. However, not every minimum dominating set is efficient. The closely related Sierpiński gasket graphs 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 n = 1 or n = 3 . Circulant graphs provide another well-studied class for efficient dominating sets. A circulant graph \text{Cay}(\mathbb{Z}_n, S) is a Cayley graph on the cyclic group \mathbb{Z}_n with connection set S , where S = -S and 0 \notin S . Such a graph has vertices \{0, 1, \ldots, n-1\} with edges connecting vertices whose difference lies in S . For a circulant graph \text{Cay}(\mathbb{Z}_n, S) to admit an efficient dominating set D , a necessary condition is n = |S_0| \cdot |D| , where S_0 = S \cup \{0\} . For connected non-complete circulant graphs of degree |S| = p - 1 where p is prime, an efficient dominating set exists if and only if s - s' \not\equiv 0 \pmod{p} for any distinct s, s' \in S_0 . When this condition holds, all efficient dominating sets are precisely the cosets g + p\mathbb{Z}_n for g \in \mathbb{Z}_n . Similar characterizations exist for circulant graphs of degree |S| = pq - 1 and |S| = p^m - 1 , where p, q are primes and m is a positive integer, provided that |S| + 1 is relatively prime to \frac{n}{|S|+1} . Stephen K. Grady, Efficient Network Domination for Life Science Applications

Text derived from https://en.wikipedia.org/w/index.php?oldid=1352730380 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.