Global dominating set
In graph theory, a global dominating set is a dominating set of a graph that is also a dominating set of the complement graph. The global domination number is the minimum cardinality of a global dominating set of. The concept was introduced by E. Sampathkumar in 1989.
Definition
Let be a graph with vertex set and edge set. A set is a dominating set of if every vertex in is adjacent to at least one vertex in. A dominating set is called a global dominating set if is also a dominating set of the complement.Equivalently, a dominating set of is a global dominating set if and only if for each vertex, there exists a vertex such that is not adjacent to in.
Properties
The following properties hold for any graph :- , where is the domination number of
- , where
- , where is the chromatic number of
Bounds
For a connected graph of order with maximum degree, diameter, radius, and the set of support vertices , the following lower bound holds:Upper bounds have also been established:
- when, where is the minimum degree
Known graphs
- For a complete graph or its complement :
- For a complete bipartite graph with :
- For a cycle with and :
- For a path with :
- For a wheel : if, and otherwise
Global domatic number
Computational complexity
The problem of finding a minimum global dominating set is NP-hard. This was established by Brigham and Dutton through a reduction from the dominating set problem, which is known to be NP-hard.The problem remains NP-hard even for restricted graph classes, including planar graphs and split graphs. For split graphs, any global dominating set is formed either by the dominating set of the graph or by the dominating set augmented with vertices from the independent set.
Algorithms
Both exact and heuristic algorithms have been developed for the global domination problem:Exact algorithms:
- An integer linear programming formulation using constraints to ensure domination in both and
- An implicit enumeration algorithm using binary search over feasible solution sizes, guided by lower and upper bounds
- Greedy algorithms that iteratively select vertices maximizing the number of newly dominated vertices in both the graph and its complement
- A purification procedure that reduces the size of a global dominating set by removing redundant vertices while maintaining the domination property
Applications
In social network analysis, when modeling individuals with certain social behaviors, a standard dominating set identifies influential individuals, but does not account for potential changes in influence relationships. A global dominating set ensures coverage even if the influence network changes to its complement, providing resilience against dynamic network changes.