Fact-checked by Grok 2 weeks ago

Dominating set

In graph theory, a dominating set of a graph G = (V, E) is a subset S \subseteq V such that every vertex in V \setminus S is adjacent to at least one vertex in S.^[1] The domination number \gamma(G) denotes the size of the smallest such dominating set, representing the minimum number of vertices needed to "dominate" the entire graph.^[2] The concept originated in the late 1950s when Claude Berge introduced it as the "coefficient of external stability" in his work on graph stability.^[1] It was formalized and named by Øystein Ore in his 1962 book Theory of Graphs, where he explored its role in covering and independence problems.^[1]^[3] Subsequent developments by researchers like E. J. Cockayne and S. T. Hedetniemi in the 1970s expanded the theory, establishing foundational results on minimal dominating sets and irredundancy.^[1] A dominating set is minimal if no proper subset dominates the graph, equivalent to being irredundant—a property where each vertex in the set has a private neighbor not dominated by others in the set.^[4] Key variants include total dominating sets, where every vertex (including those in the set) must be adjacent to another in the set, excluding isolated vertices; independent dominating sets, which are both dominating and independent (no two adjacent); and connected dominating sets, requiring the subset to induce a connected subgraph.^[1] Computing a minimum dominating set is NP-hard, even on restricted graph classes like bipartite graphs, driving research in approximation algorithms and exact solvers.^[5] Applications span wireless sensor networks for efficient broadcasting, facility location problems, cybersecurity for intrusion detection, and bioinformatics for protein interaction modeling, with 7,324 publications as of 2024 reflecting its interdisciplinary impact.^[1]

Fundamentals

Formal Definition

In graph theory, consider an undirected simple graph G = (V, E). A subset D \subseteq V is a dominating set of G if every vertex u \in V \setminus D is adjacent to at least one vertex v \in D, that is, \{u, v\} \in E.^[6] The terminology was introduced by Øystein Ore in his 1962 book Theory of Graphs.^[7] Equivalently, D is a dominating set if the union of the closed neighborhoods of its vertices covers all of V. The closed neighborhood of a vertex v \in V is defined as

N = \{ v \} \cup \{ u \in V \mid \{ u, v \} \in E \},

so D dominates G if \bigcup_{v \in D} N = V.^[6] The domination number \gamma(G) denotes the cardinality of a smallest dominating set in G.^[6] Every graph G admits at least one dominating set, for instance D = V, which trivially satisfies the condition.^[8] A dominating set D is minimal if no proper subset of D is itself a dominating set.^[9] Equivalently, every vertex in D has a private neighbor—a vertex in V that is adjacent to it but to no other vertex in D (possibly itself if isolated from the rest of D). For example, consider the path graph P_3 on vertices labeled $1, 2, 3 with edges \{1,2\} and \{2,3\}. The singleton set \{2\} is a dominating set of size 1, as vertex 1 is adjacent to 2 and vertex 3 is adjacent to 2.^[6]

Basic Properties

In graph theory, fundamental bounds on the domination number \gamma(G) of a graph G with |V(G)| = n vertices relate it to the minimum degree \delta(G) and maximum degree \Delta(G). Specifically, \gamma(G) \leq \frac{n}{1 + \delta(G)}, as demonstrated by the greedy algorithm that selects a vertex dominating at least $1 + \delta(G) vertices each time, ensuring coverage in at most \frac{n}{1 + \delta(G)} steps. Conversely, \gamma(G) \geq \frac{n}{1 + \Delta(G)}, since no vertex can dominate more than $1 + \Delta(G) vertices in its closed neighborhood. A dominating set D is minimal if no proper subset of D is dominating, meaning that removing any vertex from D fails to dominate at least one vertex in G. Moreover, every maximal independent set of G is a minimal dominating set, as it dominates all vertices (by maximality) and remains minimal due to independence—removing any vertex leaves it undominated. Additionally, if G has no isolated vertices (so \delta(G) \geq 1), then \gamma(G) \leq \frac{n}{2}, which follows from the general greedy bound \gamma(G) \leq \frac{n}{1 + \delta(G)}.

Variants and Generalizations

Classical Variants

An independent dominating set in a graph G is a dominating set that is also independent, meaning no two vertices in the set are adjacent. The independent domination number i(G) is the size of the smallest such set. This variant combines domination with the independence condition and is equivalent to the smallest maximal independent set. It plays a key role in the structure of minimal dominating sets, as every minimal dominating set is independent. A connected dominating set in a graph G is a dominating set D \subseteq V(G) such that the subgraph G[D] induced by D is connected. The connected domination number \gamma_c(G) denotes the minimum cardinality of such a set. This variant ensures not only coverage of all vertices but also connectivity within the dominating set, which is useful in network design where a backbone structure is required. The concept was introduced in the late 1970s as an extension of standard domination to address applications needing path-connected facilities.^[10] A total dominating set in a graph G is a set D \subseteq V(G) such that every vertex in V(G) has at least one neighbor in D, including vertices in D themselves; thus, G[D] contains no isolated vertices. The total domination number \gamma_t(G) is the size of the smallest total dominating set, and it satisfies \gamma_t(G) \geq \gamma(G), with existence guaranteed if and only if G has no isolated vertices. This variant strengthens the domination requirement by eliminating isolated dominators, reflecting scenarios where every facility must be supported by another. Total domination was formally defined in 1980, building on foundational work in graph domination theory.^[11] A k-dominating set in a graph G is a set D \subseteq V(G) such that every vertex not in D has at least k neighbors in D, generalizing the standard case where k=1. The k-domination number \gamma_k(G) is the minimum size of such a set, which increases with k and captures multiple-coverage needs in fault-tolerant systems. This multiple-domination variant emerged in 1985 as part of efforts to extend domination parameters for robustness analysis.^[12] An edge dominating set in a graph G=(V,E) is a subset F \subseteq E such that every edge in E \setminus F is incident to at least one edge in F. The edge domination number is the minimum cardinality of such a F, shifting focus from vertices to edges for applications like edge cover in communication networks. The problem's NP-completeness, even for planar bipartite graphs of maximum degree 3, was established in 1980.^[13] The domatic number of a graph G, denoted d(G), is the maximum number of disjoint dominating sets whose union partitions V(G), representing the finest partition into dominating sets akin to graph coloring but for domination. It satisfies d(G) \leq \delta(G) + 1, where \delta(G) is the minimum degree, and equals 1 for graphs without universal vertices. This partition-based variant was introduced in 1977 alongside core domination theory, highlighting structural decompositions.^[8] For the cycle graph C_5, the domination number is \gamma(C_5)=2, while both the connected and total domination numbers are \gamma_c(C_5)=\gamma_t(C_5)=3, illustrating how these variants impose stricter conditions leading to larger minimum sets.^[14]

Recent Variants

In recent years, research on dominating sets has introduced variants that incorporate mixed elements from vertices and edges to address more comprehensive domination requirements in graphs. A mixed dominating set in a graph G = (V, E) is a subset D \subseteq V \cup E such that every vertex in V is either in D or adjacent to a vertex or edge in D, and every edge in E is either in D or incident to a vertex or edge in D. This variant extends classical domination by ensuring coverage of both vertices and edges simultaneously. Recent algorithmic advancements, including fixed-parameter tractable algorithms running in time O(3^k \cdot n) for parameter k = |D| where n = |V|, have improved the computational tractability for finding minimum mixed dominating sets, resolving prior open questions on parameterized complexity.^[15] Another emerging variant focuses on security in network structures, particularly the secure hop dominating set. A secure hop dominating set D in a graph G is a hop dominating set—meaning every vertex not in D has a neighbor in D at distance at most two—such that for any vertex v \notin D, there exists an alternative hop dominator in D that remains effective even if an attacker removes one neighbor of v. This ensures resilience against single-point failures or attacks in applications like wireless sensor networks. Studies from 2023 to 2025 have provided bounds on the secure hop domination number, such as \gamma_{sh}(G) \leq n/2 for graphs with n vertices, and characterized graphs achieving these bounds, including paths and cycles. Notably, every graph G admits a secure hop dominating set, as the full vertex set V(G) trivially satisfies the conditions.^[16] The outer-connected fair dominating set introduces fairness and connectivity constraints to standard domination. In a graph G, an outer-connected fair dominating set D is a dominating set such that every vertex in V \setminus D has the same positive number of neighbors in D, and the subgraph induced by V \setminus D is connected. This variant is motivated by equitable resource allocation in social networks or distributed systems. Introduced in 2025, every connected non-complete graph possesses such a set, with the outer-connected fair domination number \tilde{\gamma}_{cfd}(G) ranging from \lceil n/3 \rceil to n-1 for graphs with n vertices, and exact values computed for joins of graphs like paths and cycles.^[17] Further innovations include the co-odd dominating set, which imposes parity conditions on non-dominated vertices. A co-odd dominating set D in a graph G = (V, E) is a dominating set such that every vertex in V \setminus D has odd degree in the subgraph induced by V \setminus D. This variant explores structural properties related to parity in graph domination. First defined in 2025, the co-odd domination number \gamma_{co}(G) satisfies \gamma_{co}(G) \geq \gamma(G), and minimal such sets exist in all graphs without isolated vertices.^[18] The proper 3-dominating set refines multiple domination by enforcing exact coverage. In a graph G, a proper 3-dominating set D is a 3-dominating set (every vertex in V \setminus D has at least three neighbors in D) that is not 4-dominating (at least one vertex in V \setminus D has exactly three neighbors in D). This ensures uniform triple coverage for non-members, useful in fault-tolerant designs. Results from 2025 establish that every graph with minimum degree at least 3 contains a proper 3-dominating set, with the proper 3-domination number bounded by n/2 in such cases.^[19]

Connections to Other Concepts

With Independent Sets

A maximal independent set in a graph G is always a minimal dominating set, since its independence ensures minimality and its maximality ensures that every vertex outside the set is adjacent to it. This equivalence holds because adding any vertex to a maximal independent set would violate independence, and the set already dominates the graph by construction. The converse does not hold: there exist minimal dominating sets that are not independent. For example, in the path graph P_4 with vertices labeled 1-2-3-4, the set \{2,3\} is a minimal dominating set, as neither singleton dominates the entire graph, but 2 and 3 are adjacent, so it is not independent.^[20] The independent domination number, denoted i(G), is the cardinality of a smallest independent dominating set in G. Since every independent dominating set is a dominating set, it follows that i(G) \geq \gamma(G), where \gamma(G) is the domination number. Equality holds in certain graph classes, such as claw-free graphs, where \gamma(G) = i(G).^[20] In general, however, i(G) > \gamma(G) is possible; for instance, in the double star S_{r,r} (a tree consisting of two adjacent centers each with r pendant leaves), \gamma(S_{r,r}) = 2 while i(S_{r,r}) = r+1 for r \geq 1. In the specific case of P_4, both \gamma(P_4) = 2 and i(P_4) = 2.^[20] The upper independent domination number, denoted I(G), is the cardinality of a largest minimal independent dominating set in G. This parameter captures the variability in the sizes of minimal independent dominating sets, contrasting with i(G) which focuses on the minimum; together, they bound the spectrum of such sets in graphs where independent domination plays a key role.^[21] The interplay highlights that while all maximal independent sets contribute to domination minimally and independently, the reverse requires graph-specific properties to enforce independence among dominators.^[20]

With Covering and Partitioning

The minimum dominating set problem bears a direct resemblance to the set cover problem in combinatorial optimization. To see this, consider transforming an instance of minimum dominating set on a graph G = (V, E) into a set cover instance where the universe is the vertex set V, and the available sets are the closed neighborhoods \{N \mid v \in V\}, with N = \{v\} \cup \{u \in V \mid uv \in E\}. A minimum collection of such sets that covers V precisely corresponds to a minimum dominating set of G, as each selected N ensures coverage of v and its neighbors. This polynomial-time mapping establishes an L-reduction between the problems, with approximation-preserving parameters \alpha = 1 and \beta = 1, meaning that approximation guarantees for one transfer directly to the other. A key extension of dominating sets involves partitioning the vertex set into multiple such sets, leading to the concept of the domatic number d(G). Defined as the largest integer k such that V(G) admits a partition into k disjoint dominating sets, the domatic number quantifies the graph's capacity for such coverings. Introduced by Cockayne and Hedetniemi, this parameter satisfies the upper bound d(G) \leq \delta(G) + 1, where \delta(G) is the minimum degree of G; the proof follows from observing that each dominating set in the partition must include at least one vertex from the closed neighborhood of any minimum-degree vertex, limiting the partition size.^[8]^[8] Partitions into dominating sets, particularly in regular graphs, often exhibit equitable properties, where the sizes of the individual dominating sets differ by at most one. In k-regular graphs, the symmetry facilitates such balanced domatic partitions when the order n = |V(G)| is divisible by d(G), ensuring each part has size n / d(G); this holds, for instance, in cubic graphs where d(G) = 3 almost surely for random instances, allowing equitable splits into three equal dominating sets if n is a multiple of 3. Illustrative examples highlight these properties. For the complete graph K_n, d(K_n) = n, achieved by partitioning into n singletons, each of which dominates the entire graph due to universal adjacency. In contrast, the 5-cycle C_5 has d(C_5) = 2, with a partition into dominating sets of sizes 2 and 3 (e.g., two non-adjacent vertices and the remaining three), but no valid 3-partition exists given the odd order and degree bound.^[8]^[22]

Historical Context

Origins and Early Developments

The concept of a dominating set traces its origins to the late 1950s, amid the early development of modern graph theory. In 1958, Claude Berge introduced the foundational idea in his book Théorie des graphes et ses applications, defining the "coefficient of external stability" as the cardinality of the smallest subset of vertices such that every vertex outside the subset is adjacent to at least one vertex in it. This parameter, now recognized as the domination number, marked the initial formal exploration of domination-like structures in graphs, motivated by combinatorial covering problems.^[23] The terminology evolved rapidly in the early 1960s, shifting from terms like "covering set" to the more precise "dominating set." Øystein Ore played a pivotal role in this standardization through his 1962 book Theory of Graphs, where he explicitly defined a dominating set as a subset of vertices whose closed neighborhoods cover all vertices of the graph and introduced the associated domination number. Ore's work built on Berge's concepts, emphasizing neighborhood covers and their role in graph partitioning, and included discussions of related independent and covering sets.^[24] Early research on dominating sets drew motivations from practical combinatorial challenges, including facility location problems in networks—such as optimally placing service points to cover demand—and rudimentary connections to error-correcting codes via covering configurations. A key early result came from D. R. Fulkerson and O. A. Gross in their 1965 study on incidence matrices, which explored minimal coverings in interval graphs and networks, providing structural insights applicable to domination. By 1967, Berge's Lectures on Graph Theory incorporated basic domination concepts, solidifying their place in the graph theory canon and paving the way for further developments.^[25]^[26]

Key Milestones in Complexity

In 1972, Richard M. Karp demonstrated the NP-completeness of the dominating set problem through a polynomial-time reduction from the vertex cover problem, marking a pivotal moment in establishing its computational intractability.^[27] This result built on Karp's broader classification of 21 combinatorial problems as NP-complete, highlighting the dominating set's place among fundamental hard problems in graph theory.^[28] The 1970s saw significant growth in research on dominating sets, driven by the complexity results. Researchers like E. J. Cockayne and S. T. Hedetniemi expanded the theory, establishing foundational results on minimal dominating sets and irredundancy. In the early 1980s, key variants such as total domination were introduced. Total domination, where every vertex in the graph—including those in the dominating set—must have a neighbor in the set, was formally defined and studied in the 1980 paper by E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, further broadening the theoretical framework.^[11] During the 1980s, attention shifted toward approximation techniques, with David S. Johnson's 1974 greedy algorithm—selecting vertices that cover the most uncovered nodes at each step—providing an early ln(n)-approximation for the minimum dominating set, later refined to establish bounds like O(log Δ) where Δ is the maximum degree.^[29] These developments emphasized practical solvability for large instances, influencing subsequent hardness-of-approximation results. A major milestone in the 1990s was the comprehensive surveys by Haynes, Hedetniemi, and Peter J. Slater, which cataloged over 1,000 papers on domination theory by 1998, solidifying the problem as a cornerstone of graph algorithms and complexity studies.^[30] The Parameterized Algorithms and Computational Experiments (PACE) challenges, initiated in 2016, have systematically tracked exact algorithms for dominating set, fostering progress in practical implementations.^[31] As of 2024, bibliometric analyses indicate over 7,000 publications in the field, underscoring its enduring interdisciplinary impact.^[1]

Computational Aspects

Complexity and Reductions

The dominating set problem is one of the 21 NP-complete problems identified by Karp in 1972, established via polynomial-time reduction from the set cover problem.^[32] Membership in NP follows from the existence of a certificate consisting of a candidate subset D \subseteq V; verification requires checking that every vertex in V \setminus D has at least one neighbor in D, which can be done in O(|V| + |E|) time by inspecting the adjacency list or matrix for each such vertex.^[32] The minimum dominating set problem is L-reducible to the minimum set cover problem, preserving approximation properties up to a constant factor. Given a graph G = (V, E), construct a set cover instance with universe U = V \cup \{e_v \mid v \in V\} and collection of sets \{S_v \mid v \in V\}, where each S_v = N \cup \{e_u \mid u \in N(v)\} and N = \{v\} \cup N(v) is the closed neighborhood of v. This construction runs in polynomial time, as it requires O(|V| + |E|) operations to define the sets. A minimum dominating set D \subseteq V of size \gamma(G) corresponds to selecting \{S_v \mid v \in D\}, which covers all of U: every vertex in V is in some N for v \in D, and every e_w (for w \notin D) is covered by some S_v with v \in N(w). Conversely, any set cover of size at most k yields a dominating set of size at most $2k, since uncovered vertices in V would require additional sets to cover their e_v, but the structure bounds the excess. Thus, \gamma(G) \leq \mathrm{opt}(SC) \leq 2 \cdot \gamma(G), establishing an L-reduction with parameter \alpha = 2.^[33] Conversely, the minimum set cover problem is L-reducible to the minimum dominating set problem. Given a set system with universe X and sets \mathcal{S} = \{S_1, \dots, S_m\} \subseteq 2^X, construct a graph G = (V, E) with vertex set V = X \cup \mathcal{S} (one vertex per element and per set) and edges E = \{\{x, S_i\} \mid x \in S_i, i = 1, \dots, m\}, forming a bipartite graph of incidences. This construction is polynomial-time computable in the input size. A minimum set cover C \subseteq \mathcal{S} of size \tau corresponds to the dominating set C in G: every element x \in X is adjacent to some S_i \in C (hence dominated), and every set vertex S_j \in C is included while others may require inclusion or coverage via elements, but the minimal choice aligns closely. Any dominating set of G of size at most k yields a set cover of size at most $2k, as selected set vertices directly cover elements, and selected elements can be replaced by one incident set each without increasing size beyond a factor of 2. Thus, \tau \approx \gamma(G) within a constant factor, confirming the L-reduction.^[33] The NP-hardness of dominating set extends to restricted graph classes. In particular, deciding whether a planar graph with maximum degree \Delta = 3 has a dominating set of size at most k is NP-complete, as shown via reduction from exact cover by 3-sets while preserving planarity and degree bounds.

Approximation and Exact Algorithms

The minimum dominating set problem is NP-hard and admits no polynomial-time algorithm unless P = NP. It is also APX-complete, even when restricted to graphs with maximum degree 3. A standard approximation approach is the greedy algorithm, which iteratively selects the vertex whose closed neighborhood covers the maximum number of yet uncovered vertices until the entire graph is dominated. This method yields a dominating set of size at most H_n times the optimum, where H_n is the n-th harmonic number (approximately ln n + 1). The performance guarantee was established by Johnson in 1974 as part of broader results on set cover approximations, with the tight bound proven by Chvátal in 1979. Constant-factor approximations are known for planar graphs, including a PTAS. Exact algorithms rely on branching strategies, often analyzed via measure-and-conquer to obtain tight time bounds. A key method branches on the closed neighborhood of an undominated vertex, reducing the instance recursively while bounding the search tree size. van Rooij, Nederlof, and van der Zwaan applied measure-and-conquer in 2009 to analyze such a branching algorithm, yielding a time complexity of O(1.5048^n). Subsequent refinements have improved the bound to O(1.4969^n) as of 2017. For trees, dynamic programming enables exact solutions in linear time. The algorithm performs a post-order traversal, computing for each subtree the minimum dominating set sizes under cases where the root is dominated by itself, its parent, or a child. This yields O(n time overall. While centroid decomposition can facilitate balanced recursion in related problems, the standard tree DP suffices for minimum dominating sets without it.

Parameterized Complexity

The parameterized complexity of the Dominating Set problem, parameterized by the solution size k, is W^[34]-complete. This hardness result, established through fpt-reductions from problems like Set Cover, implies that no fixed-parameter tractable (FPT) algorithm exists unless FPT = W^[34]. Despite this intractability on general graphs, the problem is FPT on planar graphs, with an algorithm running in O(2^{O(\sqrt{k})} n) time achieved via kernelization to an instance of size O(k).^[35] This approach relies on structural properties of planar graphs, such as bounded treewidth in subgraphs, to reduce the instance before applying bounded-search-tree techniques. Regarding kernelization, no $2k-vertex kernel exists for general graphs, as the problem lacks even a quadratic kernel unless coNP \subseteq NP/poly. However, an O(k^2)-vertex kernel is known for claw-free graphs, obtained by iteratively applying reduction rules that bound the number of vertices not covered by small dominating sets. Recent advancements from 2020 to 2025 have yielded improved linear kernels for graphs of bounded degree, leveraging expansion properties and crown decompositions to reduce instances to O(dk) vertices, where d is the maximum degree.^[36]^[37] When parameterized by treewidth tw, Dominating Set is FPT, solvable in O(3^{tw} n) time using dynamic programming over a tree decomposition. This exploits the linear structure of the decomposition to track partial dominating sets in bags, with states representing coverage of bag vertices. Applications of Courcelle's theorem further confirm FPT status for monadic second-order expressible variants on bounded treewidth graphs.^[38] The PACE 2025 challenge evaluated exact solvers for Dominating Set on large instances, benchmarking algorithms on graphs up to thousands of vertices and highlighting practical performance of hybrid approaches combining kernelization, branching, and measure-and-conquer strategies.^[39] Under above-guarantee parameterization, where the solution size k \geq \gamma(G)/c for constant c > 1 and \gamma(G) is the domination number, the problem is FPT, as the excess over the guarantee allows randomized selection and branching with small failure probability.^[40]

References

[1]
None
### Definition, History, Importance, and Key Aspects of Dominating Sets in Graph Theory
[2]
[PDF] Dominating Sets in Grid arXiv:1707.06471v3 [cs.DM] 15 Mar 2018
Mar 15, 2018 · A subset S of vertices is a dominating set if every vertex not in S has at least one neighbor in S. A dominating set with minimum cardinality is ...Missing: Ore | Show results with:Ore
[3]
Theory of graphs : Ore, Øystein, 1899-1968 - Internet Archive
Apr 25, 2023 · Graph theory, Graphes, Théorie des ... Dominating sets, covering sets and independent sets -- Chromatic graphs -- Groups and graphs.
[4]
Dominating Set -- from Wolfram MathWorld
A dominating set is minimal dominating iff it is irredundant (Mynhardt and Roux 2020). Precomputed dominating sets for many named graphs can be obtained in the ...
[5]
Computer Science > Machine Learning - arXiv
Jun 6, 2023 · The minimum dominating set problem seeks to find a dominating set of minimum cardinality and is a well-established NP-hard combinatorial ...
[6]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book introduces graph theory, presenting basic material and applications to math and real-world problems, with new proofs and efficient methods.<|control11|><|separator|>
[7]
Theory of graphs : Ore, Øystein, 1899-1968 - Internet Archive
Aug 7, 2019 · Theory of graphs. by: Ore, Øystein, 1899-1968. Publication date: 1962. Topics: Graph theory. Publisher: Providence, American Mathematical ...
[8]
Towards a theory of domination in graphs - Wiley Online Library
This paper presents a quick review of results and applications concerning dominating sets in graphs. The domatic number of a graph is defined and studied.Missing: survey | Show results with:survey
[9]
[PDF] On maximum number of minimal dominating sets in graphs
dominating set is minimal if all its proper subsets are not dominating. We define DOM(G) to be the number of minimal dominating sets in a graph. G. The ...Missing: source | Show results with:source
[10]
(PDF) The connected domination number of a graph - ResearchGate
This paper investigates the connected equitable domination in the join and corona of graphs.
[11]
Total domination in graphs - Cockayne - 1980 - Wiley Online Library
A set D of vertices of a finite, undirected graph G = (V, E) is a total dominating set if every vertex of V is adjacent to some vertex of D.
[12]
[PDF] Bounds on the k-Domination Number of a Graph - Clemson University
Jan 5, 2011 · The k-domination number of a graph is the cardinality of a smallest set of vertices such that every vertex not in the set is adjacent to at ...<|separator|>
[13]
Edge Dominating Sets in Graphs - SIAM.org
A dominating set $D$ in a graph is a subset of its vertex set such that each vertex is either in $D$ or has a neighbor in $D$. In this paper, we are interested ...Missing: original | Show results with:original
[14]
[PDF] γ-total dominating graphs of paths and cycles
A set D ⊆ V(G) is called a dominating set if every vertex in V(G)\D is adjacent to some vertex in D. The domination number of G, denoted by γ(G), is the minimum ...
[15]
[PDF] New Algorithms for Mixed Dominating Set
Apr 26, 2021 · We study the complexity of exact and parameterized algorithms for MIXED DOMINATING SET, resolving some open questions.
[16]
Secure Hop Dominating Sets in Graphs
May 1, 2025 · We characterize the secure hop dominating sets in the shadow graph and complementary prism and determine the value of the parameter for each of these graphs.Missing: 2023-2025 | Show results with:2023-2025
[17]
[PDF] Outer-Connected Fair Domination in Graphs - IJFMR
The outer-connected fair domination number of 𝐺 is the minimum cardinality of an outer-connected fair dominating set of 𝐺, denoted by 𝛾̃𝑐𝑓𝑑(G). In this paper, we ...
[18]
[PDF] Co-odd domination in graphs - Shahin Digital Publisher
Jun 13, 2025 · A dominating set D in a graph Γ with vertex set V is said to be a co-odd dominating set if the degree of every vertex belonging to V \D is odd.
[19]
Proper 3-Dominating Sets in Graphs - MDPI
A dominating set is a classic concept that is widely used in road safety, disaster rescue operations, and chemical graphs.
[20]
[PDF] Dominating sets in graph theory and algebraic hyperstructures
One investigation focuses on regular relations in two types of hypergroups: one derived from the vertices of a hypergraph and the other from its edges, which.
[21]
Independent domination in graphs: A survey and recent results
Apr 6, 2013 · The theory of independent domination was formalized by Berge [6] and Ore [91] in 1962. The independent domination number and the notation were ...
[22]
(PDF) Γ-independent dominating graphs of paths and cycles
Nov 21, 2024 · The upper independent domination number of a graph G, denoted by Γi(G), is the maximum cardinality of a minimal independent dominating set of G.
[23]
[PDF] Fractional Domatic, Idomatic and Total Domatic Numbers of a Graph
The fractional domatic number of a graph G is the maximum ratio. |F|/m(F) over all families F of dominating sets of G, where m(F) denotes.
[24]
[PDF] Domination in Graphs - Digital Commons @ USF
May 19, 2010 · Oystein. Ore [39] introduced the terms “dominating set” and “domination number” in his book on graph theory which was published in 1962. The ...
[25]
THEORY OF GRAPHS - OYSTEIN ORE - Google Books
Bibliographic information ; Title, THEORY OF GRAPHS ; Author, OYSTEIN ORE ; Published, 1962 ; Export Citation, BiBTeX EndNote RefMan ...Missing: PDF online
[26]
INCIDENCE MATRICES AND INTERVAL GRAPHS - Project Euclid
D. R. FULKERSON AND 0. A. GROSS. It would be interesting to know conditions on ATA in order that. A have the consecutive Γs property. Although we have not ...Missing: networks | Show results with:networks
[27]
Lectures on Graph Theory - Claude Berge - Google Books
Claude Berge. Tata Institute of Fundamental Research, 1967 - Graph theory - 100 pages. From inside the book. Contents. Internal Stability Number of a Graph. 14.
[28]
[PDF] Reducibility Among Combinatorial Problems - Semantic Scholar
Reducibility Among Combinatorial Problems. @inproceedings ... 1973. A large class of combinatorial problems have been shown by Cook and Karp to be computationally ...
[29]
Reducibility among Combinatorial Problems - SpringerLink
Reducibility among Combinatorial Problems. Chapter. pp 85–103; Cite this chapter. Download book PDF.
[30]
Approximation algorithms for combinatorial problems - ScienceDirect
December 1974, Pages 256-278. Journal of Computer and System Sciences. Approximation algorithms for combinatorial problems*. Author links open overlay panel
[31]
Fundamentals of Domination in Graphs - Taylor & Francis eBooks
Dec 16, 2013 · "Provides the first comprehensive treatment of theoretical, algorithmic, and application aspects of domination in graphs-discussing fundamental ...
[32]
News · PACE Challenge
We have prepared a preliminary set of 50 instances for the exact track of the Dominating Set Challenge. ... PACE 2025: Verifiers and small test sets are available ...Pace 2025 · Pace 2026 · About · Newsletter
[33]
[PDF] REDUCIBILITY AMONG COMBINATORIAL PROBLEMS
REDUCIBILITY AMONG COMBINATORIAL PROBLEMS. 87 elements of other countable domains. It is a reasonable working hypothesis, championed originally by Jack ...
[34]
[PDF] On the Approximability of NP-complete Optimization Problems
This thesis deals with the polynomial approximability of NP-complete combinatorial optimization problems, exploring different measures of approximation quality.
[35]
[PDF] A 2-Approximation Algorithm for Dominating Sets - HAL
We rigorously prove that our algorithm achieves a 2- approximation ratio, ensuring that the size of the dominating set it produces is at most twice that of the ...
[36]
Polynomial-time data reduction for dominating set | Journal of the ACM
This paper demonstrates data reduction for the NP-complete Dominating Set problem, proving a linear size kernel for planar graphs using simple reduction rules.Missing: original | Show results with:original
[37]
[1012.0012] Domination When the Stars Are Out - arXiv
Nov 30, 2010 · We show that Dominating Set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel.
[38]
[PDF] A General Kernelization Technique for Domination and ... - DROPS
Dominating Set is arguably one of the touchstone for kernelization in sparse graph classes: after a linear kernel in planar graphs [1] and a polynomial kernel ...Missing: 2020-2025 | Show results with:2020-2025
[39]
Dominating set is fixed parameter tractable in claw-free graphs
Nov 25, 2011 · We present an algorithm that uses 2 O ( k 2 ) n O ( 1 ) time and polynomial space to decide whether a claw-free graph on n vertices has a ...
[40]
PACE 2025 - Dominating Set
A dominating set for a graph is a set such that every vertex or one of its neighbors is contained in , that is, for all we have or there is with .
[41]
[PDF] Domination Above r-Independence: Does Sparseness Help? - DROPS
Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a ...