The Diameter of Connected Domination

Abstract

Let \(\gamma_c(G)\) be the connected domination number of \(G\).A graph is \(k\)-\(\gamma_c\)-critical if \(\gamma_c(G) = k\) and \(\gamma_c(G + uv) < \gamma_c(G)\) for any nonadjacent pair of vertices \(u\) and \(v\) in the graph \(G\). In this paper, we show that the diameter of a \(k\)-\(\gamma_c\)-critical graph is at most \(k\) and this upper bound is sharp.