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 (or g.d. 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

For a graph of order without isolated vertices:

, where is the chromatic number of

The global domination number exhibits invariance under certain graph operations. For example, for cycles (with ), the global domination number remains unchanged under the operation of edge duplication, and similarly for wheels .

Bounds

For a connected graph of order with maximum degree , diameter , radius , and the set of support vertices (vertices adjacent to vertices with degree ) , the following lower bound holds:

Upper bounds have also been established:

when , where is the minimum degree

Known graphs

For specific families of graphs, the global domination number has been determined:

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

The global domatic number is the maximum order of a partition of the vertex set into global dominating sets. Analogous to the relationship between the domination number and domatic number, we have and , where is the domatic number and is the minimum degree of .

Computational complexity

The problem of finding a minimum global dominating set is NP-hard. This was established by Brigham and Dutton (1990) 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 (ILP) 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

Heuristic algorithms:

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

Global dominating sets arise naturally in network reliability contexts. Consider a graph representing a network of roads connecting various locations, where some locations have supply stations. If the primary links (edges of ) may fail, maintaining supply requires that stations can reach all locations through alternative links (edges of ). A global dominating set represents the minimum set of supply stations needed to maintain service regardless of which network (primary or backup) is operational.

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.