Global dominating set

☆ Save On Wikipedia ↗
Two complementary graphs, with a minimum global dominating set colored red in each

In graph theory, a global dominating set is a dominating set S {\displaystyle S} {\displaystyle S} of a graph G {\displaystyle G} {\displaystyle G} that is also a dominating set of the complement graph G ¯ {\displaystyle {\bar {G}}} {\displaystyle {\bar {G}}}. The global domination number γ g ( G ) {\displaystyle \gamma _{g}(G)} {\displaystyle \gamma _{g}(G)} is the minimum cardinality of a global dominating set of G {\displaystyle G} {\displaystyle G}. The concept was introduced by E. Sampathkumar in 1989.[1]

Definition

Let G = ( V , E ) {\displaystyle G=(V,E)} {\displaystyle G=(V,E)} be a graph with vertex set V {\displaystyle V} {\displaystyle V} and edge set E {\displaystyle E} {\displaystyle E}. A set S ⊆ V {\displaystyle S\subseteq V} {\displaystyle S\subseteq V} is a dominating set of G {\displaystyle G} {\displaystyle G} if every vertex in V − S {\displaystyle V-S} {\displaystyle V-S} is adjacent to at least one vertex in S {\displaystyle S} {\displaystyle S}. A dominating set S {\displaystyle S} {\displaystyle S} is called a global dominating set (or g.d. set) if S {\displaystyle S} {\displaystyle S} is also a dominating set of the complement G ¯ {\displaystyle {\bar {G}}} {\displaystyle {\bar {G}}}.[1]

Equivalently, a dominating set S {\displaystyle S} {\displaystyle S} of G {\displaystyle G} {\displaystyle G} is a global dominating set if and only if for each vertex v ∈ V − S {\displaystyle v\in V-S} {\displaystyle v\in V-S}, there exists a vertex u ∈ S {\displaystyle u\in S} {\displaystyle u\in S} such that u {\displaystyle u} {\displaystyle u} is not adjacent to v {\displaystyle v} {\displaystyle v} in G {\displaystyle G} {\displaystyle G}.[1]

Properties

The following properties hold for any graph G {\displaystyle G} {\displaystyle G}:[1]

  • γ g ( G ) = γ g ( G ¯ ) {\displaystyle \gamma _{g}(G)=\gamma _{g}({\bar {G}})} {\displaystyle \gamma _{g}(G)=\gamma _{g}({\bar {G}})}
  • γ ( G ) ≤ γ g ( G ) {\displaystyle \gamma (G)\leq \gamma _{g}(G)} {\displaystyle \gamma (G)\leq \gamma _{g}(G)}, where γ ( G ) {\displaystyle \gamma (G)} {\displaystyle \gamma (G)} is the domination number of G {\displaystyle G} {\displaystyle G}
  • γ ¯ ( G ) ≤ γ g ( G ) {\displaystyle {\bar {\gamma }}(G)\leq \gamma _{g}(G)} {\displaystyle {\bar {\gamma }}(G)\leq \gamma _{g}(G)}, where γ ¯ ( G ) = γ ( G ¯ ) {\displaystyle {\bar {\gamma }}(G)=\gamma ({\bar {G}})} {\displaystyle {\bar {\gamma }}(G)=\gamma ({\bar {G}})}
  • γ ( G ) + γ ¯ ( G ) 2 ≤ γ g ( G ) ≤ γ ( G ) + γ ¯ ( G ) {\displaystyle {\frac {\gamma (G)+{\bar {\gamma }}(G)}{2}}\leq \gamma _{g}(G)\leq \gamma (G)+{\bar {\gamma }}(G)} {\displaystyle {\frac {\gamma (G)+{\bar {\gamma }}(G)}{2}}\leq \gamma _{g}(G)\leq \gamma (G)+{\bar {\gamma }}(G)}

For a graph G {\displaystyle G} {\displaystyle G} of order p {\displaystyle p} {\displaystyle p} without isolated vertices:[1]

  • γ ( G ) + γ g ( G ) ≤ p + 1 {\displaystyle \gamma (G)+\gamma _{g}(G)\leq p+1} {\displaystyle \gamma (G)+\gamma _{g}(G)\leq p+1}
  • γ g ( G ) ≤ max { χ ( G ) , χ ( G ¯ ) } {\displaystyle \gamma _{g}(G)\leq \max\{\chi (G),\chi ({\bar {G}})\}} {\displaystyle \gamma _{g}(G)\leq \max\{\chi (G),\chi ({\bar {G}})\}}, where χ ( G ) {\displaystyle \chi (G)} {\displaystyle \chi (G)} is the chromatic number of G {\displaystyle G} {\displaystyle G}

The global domination number exhibits invariance under certain graph operations. For example, for cycles C n {\displaystyle C_{n}} {\displaystyle C_{n}} (with n ≠ 3 , n ≠ 5 {\displaystyle n\neq 3,n\neq 5} {\displaystyle n\neq 3,n\neq 5}), the global domination number remains unchanged under the operation of edge duplication, and similarly for wheels W n {\displaystyle W_{n}} {\displaystyle W_{n}}.[2]

Bounds

For a connected graph G {\displaystyle G} {\displaystyle G} of order n {\displaystyle n} {\displaystyle n} with maximum degree Δ ( G ) {\displaystyle \Delta (G)} {\displaystyle \Delta (G)}, diameter d ( G ) {\displaystyle d(G)} {\displaystyle d(G)}, radius r ( G ) {\displaystyle r(G)} {\displaystyle r(G)}, and the set of support vertices (vertices adjacent to vertices with degree 1 {\displaystyle 1} {\displaystyle 1}) S u p p ( G ) {\displaystyle Supp(G)} {\displaystyle Supp(G)}, the following lower bound holds:[3]

L = max { n Δ ( G ) + 1 , 2 r ( G ) 3 , d ( G ) + 1 3 , | S u p p ( G ) | } ≤ γ g ( G ) {\displaystyle L=\max \left\{{\frac {n}{\Delta (G)+1}},{\frac {2r(G)}{3}},{\frac {d(G)+1}{3}},|Supp(G)|\right\}\leq \gamma _{g}(G)} {\displaystyle L=\max \left\{{\frac {n}{\Delta (G)+1}},{\frac {2r(G)}{3}},{\frac {d(G)+1}{3}},|Supp(G)|\right\}\leq \gamma _{g}(G)}

Upper bounds have also been established:[3]

  • γ g ( G ) ≤ min { Δ ( G ) , Δ ( G ¯ ) } + 1 {\displaystyle \gamma _{g}(G)\leq \min\{\Delta (G),\Delta ({\bar {G}})\}+1} {\displaystyle \gamma _{g}(G)\leq \min\{\Delta (G),\Delta ({\bar {G}})\}+1}
  • γ g ( G ) ≤ max { δ ( G ) , δ ( G ¯ ) } + 1 {\displaystyle \gamma _{g}(G)\leq \max\{\delta (G),\delta ({\bar {G}})\}+1} {\displaystyle \gamma _{g}(G)\leq \max\{\delta (G),\delta ({\bar {G}})\}+1} when δ ( G ) = δ ( G ¯ ) > 2 {\displaystyle \delta (G)=\delta ({\bar {G}})>2} {\displaystyle \delta (G)=\delta ({\bar {G}})>2}, where δ ( G ) {\displaystyle \delta (G)} {\displaystyle \delta (G)} is the minimum degree

Known graphs

For specific families of graphs, the global domination number has been determined:[1][2]

  • For a complete graph K p {\displaystyle K_{p}} {\displaystyle K_{p}} or its complement K ¯ p {\displaystyle {\bar {K}}_{p}} {\displaystyle {\bar {K}}_{p}}: γ g ( G ) = p {\displaystyle \gamma _{g}(G)=p} {\displaystyle \gamma _{g}(G)=p}
  • For a complete bipartite graph K m , n {\displaystyle K_{m,n}} {\displaystyle K_{m,n}} with 2 ≤ m ≤ n {\displaystyle 2\leq m\leq n} {\displaystyle 2\leq m\leq n}: γ g ( K m , n ) = n {\displaystyle \gamma _{g}(K_{m,n})=n} {\displaystyle \gamma _{g}(K_{m,n})=n}
  • For a cycle C n {\displaystyle C_{n}} {\displaystyle C_{n}} with n ≠ 3 {\displaystyle n\neq 3} {\displaystyle n\neq 3} and n ≠ 5 {\displaystyle n\neq 5} {\displaystyle n\neq 5}: γ g ( C n ) = ⌈ n / 3 ⌉ {\displaystyle \gamma _{g}(C_{n})=\lceil n/3\rceil } {\displaystyle \gamma _{g}(C_{n})=\lceil n/3\rceil }
  • For a path P n {\displaystyle P_{n}} {\displaystyle P_{n}} with n ≥ 4 {\displaystyle n\geq 4} {\displaystyle n\geq 4}: γ g ( P n ) = ⌈ n / 3 ⌉ {\displaystyle \gamma _{g}(P_{n})=\lceil n/3\rceil } {\displaystyle \gamma _{g}(P_{n})=\lceil n/3\rceil }
  • For a wheel W n {\displaystyle W_{n}} {\displaystyle W_{n}}: γ g ( W n ) = 4 {\displaystyle \gamma _{g}(W_{n})=4} {\displaystyle \gamma _{g}(W_{n})=4} if n = 4 {\displaystyle n=4} {\displaystyle n=4}, and γ g ( W n ) = 3 {\displaystyle \gamma _{g}(W_{n})=3} {\displaystyle \gamma _{g}(W_{n})=3} otherwise

Global domatic number

The global domatic number d g ( G ) {\displaystyle d_{g}(G)} {\displaystyle d_{g}(G)} is the maximum order of a partition of the vertex set V {\displaystyle V} {\displaystyle V} into global dominating sets. Analogous to the relationship between the domination number and domatic number, we have d g ( G ) = d g ( G ¯ ) {\displaystyle d_{g}(G)=d_{g}({\bar {G}})} {\displaystyle d_{g}(G)=d_{g}({\bar {G}})} and d g ( G ) ≤ d ( G ) ≤ δ ( G ) + 1 {\displaystyle d_{g}(G)\leq d(G)\leq \delta (G)+1} {\displaystyle d_{g}(G)\leq d(G)\leq \delta (G)+1}, where d ( G ) {\displaystyle d(G)} {\displaystyle d(G)} is the domatic number and δ ( G ) {\displaystyle \delta (G)} {\displaystyle \delta (G)} is the minimum degree of G {\displaystyle G} {\displaystyle G}.[1]

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.[3][4]

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.[3]

Algorithms

Both exact and heuristic algorithms have been developed for the global domination problem:[3]

Exact algorithms:

  • An integer linear programming (ILP) formulation using 2 n {\displaystyle 2n} {\displaystyle 2n} constraints to ensure domination in both G {\displaystyle G} {\displaystyle G} and G ¯ {\displaystyle {\bar {G}}} {\displaystyle {\bar {G}}}
  • 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 G {\displaystyle G} {\displaystyle G}) may fail, maintaining supply requires that stations can reach all locations through alternative links (edges of G ¯ {\displaystyle {\bar {G}}} {\displaystyle {\bar {G}}}). A global dominating set represents the minimum set of supply stations needed to maintain service regardless of which network (primary or backup) is operational.[1]

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.[3]

References

  1. Sampathkumar, E. (1989). "The global domination number of a graph". Journal of Mathematical and Physical Sciences. 23 (5): 377–385.
  2. Vaidya, S. K.; Pandit, R. M. (2013). "Some New Perspectives on Global Domination in Graphs". ISRN Combinatorics. 2013: 1–4. doi:10.1155/2013/201654.
  3. Parra Inza, Ernesto; Vakhania, Nodari; Sigarreta Almira, José María; Hernández Mira, Frank Angel (2024). "Algorithms for the Global Domination Problem". Computers & Operations Research. 172 106876. arXiv:2312.04526. doi:10.1016/j.cor.2024.106876.
  4. Brigham, R. C.; Dutton, R. D. (1990). "Factor domination in graphs". Discrete Mathematics. 86 (1–3): 127–136. doi:10.1016/0012-365X(90)90355-L.

Further reading