An Inequality on Connected Domination Parameters

Abstract

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)\le 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.