An Inequality on Connected Domination Parameters

Let \(G = (V,E)\) be a connected graph. Let \(\gamma_c(G), d_c(G)\) denote the connected domination number, connected domatic number of \(G\), respectively. We prove that \(\gamma_c(G) \leq 3d_c(G^c)\) if the complement of \(G\) is also connected. This confirms a conjecture of Hedetniemi and Laskar (1984), and Sun (1992). Examples are given to show that equality may occur.