A Note on Global Domination in Graphs

Abstract

Let \(G = (V, E)\) be a graph. A subset \(S\) of \(V\) is called a dominating set of \(G\) if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A global dominating set is a subset \(S\) of \(V\) which is a dominating set of both \(G\) as well as its complement \(\overline{G}\). The domination number (global domination number) \(\gamma(\gamma_g)\) of \(G\) is the minimum cardinality of a dominating set (global dominating set) of \(G\). In this paper, we obtain a characterization of bipartite graphs with \(\gamma_g = \gamma + 1\). We also characterize unicyclic graphs and bipartite graphs with \(\gamma_g = \alpha_0(G) + 1\), where \(\alpha_0(G)\) is the vertex covering number of \(G\).