Nordhaus–Gaddum type results for connected and total domination
Rana Khoeilar, Hossein Karami, Mustapha Chellali, Seyed Mahmoud Sheikholeslami, Lutz Volkmann · RAIRO - Operations Research · 2020
A dominating set of G = (V, E) is a subset S of V such that every vertex in V − S has at least one neighbor in S. A connected dominating set of G is a dominating set whose induced subgraph is connected. The minimum cardinality of a connected dominating set is the connected domination number γc(G). Let δ*(G) = min{δ(G), δ(G̅)}, where G̅ is the complement of G and δ(G) is the minimum vertex degree. In this paper, we improve upon existing results by providing new Nordhaus–Gaddum type results for connected domination. In particular, we show that if G and G̅ are both connected and min{γc(G), γc(G̅)} ≥ 3, then $ {\gamma }_c(G)+{\gamma }_c(\bar{G})\le 4+({\delta }^{\mathrm{*}}(G)-1)\left(\frac{1}{{\gamma }_c(G)-2}+\frac{1}{{\gamma }_c(\bar{G})-2}\right)$ and $ {\gamma }_c(G){\gamma }_c(\bar{G})\le 2({\delta }^{\mathrm{*}}(G)-1)\left(\frac{1}{{\gamma }_c(G)-2}+\frac{1}{{\gamma }_c(\bar{G})-2}+\frac{1}{2}\right)+4$ . Moreover, we establish accordingly results for total domination.