Nordhaus–Gaddum type results for connected and total domination

¹ Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran
² LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
³ Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany

^* Corresponding author: khoeilar@azaruniv.ac.ir

Received: 13 September 2019
Accepted: 26 February 2020

Abstract

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\left(G\right)+{\gamma }_c\left(\bar{G}\right)\le 4+\left({\delta }^{\mathrm{*}}\right(G)-1)\left(\frac{1}{{\gamma }_c\left(G\right)-2}+\frac{1}{{\gamma }_c\left(\bar{G}\right)-2}\right)$ and ${\gamma }_c\left(G\right){\gamma }_c\left(\bar{G}\right)\le 2\left({\delta }^{\mathrm{*}}\right(G)-1)\left(\frac{1}{{\gamma }_c\left(G\right)-2}+\frac{1}{{\gamma }_c\left(\bar{G}\right)-2}+\frac{1}{2}\right)+4$. Moreover, we establish accordingly results for total domination.