Connected domination critical graphs Original Research Article

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The minimum number of vertices in a connected dominating set of G is called the connected domination number of G, and is denoted by γc(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: for each υ, μ ϵ V (G) with υ not adjacent to u, γc(G + υu) < γc(G). Thus, G is k-γc-critical if γc(G) = k and for each edge e ∉ E(G), γc(G + e) < k. First we discuss whether some particular classes of graphs are γc-critical. Then 2-γc-critical graphs are characterized. Finally, the properties of the 3-γc-critical graphs are studied.