×

A note on global domination in graphs. (English) Zbl 1224.05357

Summary: 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+1\), where \(\alpha _0\) is the vertex covering number of \(G\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite