Matching properties in connected domination critical graphs

A dominating set of vertices SS of a graph GG is connected if the subgraph G[S]G[S] is connected. Let γc(G)γc(G) denote the size of any smallest connected dominating set in GG. A graph GG is kk-γγ-connected-critical if γc(G)=kγc(G)=k, but if any edge e∈E(G¯) is added to GG, then γc(G+e)⩽k-1γc(G+e)⩽k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph GG was defined to be kk-critical if the domination number of GG is kk, but if any edge is added to GG, the domination number falls to k-1k-1.A graph GG is factor-critical if G-vG-v has a perfect matching for every vertex v∈V(G)v∈V(G), bicritical if G-u-vG-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G)u,v∈V(G) or, more generally, kk-factor-critical if, for every set S⊆V(G)S⊆V(G) with |S|=k|S|=k, the graph G-SG-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1–13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph GG with (ordinary) domination number 3 will be factor-critical (if |V(G)||V(G)| is odd), bicritical (if |V(G)||V(G)| is even) or 3-factor-critical (again if |V(G)||V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1–13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].