On 4-γc-critical graphs with cut-vertices

Abstract

Let γ_c (G) denote the connected domination number of a graph G. G is said to be k-γ_c-critical if γ _c(G) = k and for each pair of non-adjacent vertices u and t; of G, γ_c(G + uv) < k. In this paper, we show that 4-γ_c-critical graphs contain at most two cut-vertices. A characterization of 4-γ_c-critical graphs containing exactly two cut-vertices is given. We also establish that a 4-γ_c-critical graph of even order having connectivity one contains a perfect matching.