Connected Domination Critical Graphs with Cut Vertices

A graph G is said to be k-γ_c-critical if the connected domination number of G, γ_c(G), is k and γ_c(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γ_c-critical graph and ζ (G) the number of cut vertices of G. It was proved, in [1, 6], that, for 3 ≤ k ≤ 4, every k-γ_c-critical graph satisfies ζ (G) ≤ k − 2. In this paper, we generalize that every k-γ_c-critical graph satisfies ζ (G) ≤ k − 2 for all k ≥ 5. We also characterize all k-γ_c-critical graphs when ζ(G) is achieving the upper bound.