In graph theory, a global dominating set is a dominating set S {\displaystyle S} of a graph G {\displaystyle G} that is also a dominating set of the complement graph G ¯ {\displaystyle {\bar {G}}} . The global domination number γ g ( G ) {\displaystyle \gamma _{g}(G)} is the minimum cardinality of a global dominating set of G {\displaystyle G} . The concept was introduced by E. Sampathkumar in 1989.
Definition Let G = ( V , E ) {\displaystyle G=(V,E)} be a graph with vertex set V {\displaystyle V} and edge set E {\displaystyle E} . A set S ⊆ V {\displaystyle S\subseteq V} is a dominating set of G {\displaystyle G} if every vertex in V − S {\displaystyle V-S} is adjacent to at least one vertex in S {\displaystyle S} . A dominating set S {\displaystyle S} is called a global dominating set (or g.d. set) if S {\displaystyle S} is also a dominating set of the complement G ¯ {\displaystyle {\bar {G}}} . Equivalently, a dominating set S {\displaystyle S} of G {\displaystyle G} is a global dominating set if and only if for each vertex v ∈ V − S {\displaystyle v\in V-S} , there exists a vertex u ∈ S {\displaystyle u\in S} such that u {\displaystyle u} is not adjacent to v {\displaystyle v} in G {\displaystyle G} .
Properties The following properties hold for any graph G {\displaystyle G} :
γ g ( G ) = γ g ( G ¯ ) {\displaystyle \gamma _{g}(G)=\gamma _{g}({\bar {G}})}
γ ( G ) ≤ γ g ( G ) {\displaystyle \gamma (G)\leq \gamma _{g}(G)} , where γ ( G ) {\displaystyle \gamma (G)} is the domination number of G {\displaystyle G}
γ ¯ ( G ) ≤ γ g ( G ) {\displaystyle {\bar {\gamma }}(G)\leq \gamma _{g}(G)} , where γ ¯ ( G ) = γ ( 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)}
For a graph G {\displaystyle G} of order p {\displaystyle p} without isolated vertices:
γ ( G ) + γ g ( G ) ≤ 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}})\}} , where χ ( G ) {\displaystyle \chi (G)} is the chromatic number of G {\displaystyle G}
… excerpt ends here. Continue reading the full article.
