Connected domination: Vertex criticality and matchings
Abstract
A dominating set of vertices S in a graph G is connected if the induced subgraph G[S] is connected. Let γc(G) denote the size of any smallest connected dominating set in G. Graph G is k-connectedvertex-critical if γC(G) = k, but if any vertex v is deleted from G, then γc(G-v) ≤ k-1. A graph G is factor-critical if G - v has a perfect matching for every vertex v ⋯ V(G), bicritical if G - u - v has a perfect matching for every pair of distinct vertices u, v ⋯ V(G) or, more generally, kfactor-critical if, for every set S ⊆ V(G) with |S| = k, the graph G - S contains a perfect matching. In several previous papers on vertex criticality for ordinary (i.e., not necessarily connected) domination, the second and third authors showed that under certain assumptions regarding connectivity and minimum degree, a vertex-critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if | V(G)| is odd). Analogous theorems for connected domination are presented here. It should be noted that although vertex criticality for domination and connected domination are similar in some ways, some interesting differences are to be found in these new results and techniques for the case of connected domination when compared with those for ordinary domination.
