An inequality on connected domination parameters (Q2713663)

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). If moreover the subgraph of \(G\) induced by \(S\) is connected, \(S\) is called a connected dominating set in \(G\). The minimum number of vertices of a connected dominating set in \(G\) is the connected domination number \(\gamma _c(G)\) of \(G\). The minimum number of classes of a partition of \(V(G)\), all of whose classes are connected dominating sets in \(G\), is the connected domatic number \(d_c(G)\) of \(G\). The paper presents the inequality \(\gamma _c (G) \leq 3d_c (G^c)\), where \(G^c\) is the complement of \(G\), whenever both \(G\) and \(G^c\) are connected.