Vertex criticality for connected domination
Abstract
A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γc(G) denote the size of any smallest connected dominating set in G. Graph G is k-connected-vertex-critical (abbreviated "kcvc") if γC(G) = k, but if any vertex v is deleted from G, then γC(G - v) ≤ k - 1. This concept of vertex criticality stands in contrast to the concept of criticality with respect to edge addition in which a graph G is defined to be k-connected-critical if the connected domination number of G is k, but if any edge is added to G, the connected domination number of the resulting graph is at most k -1. It is well-known that the only 1cvc graph is K1 and the 2cvc graphs are obtained from the even complete graphs K2n, with n ≥ 2, by deleting a perfect matching. In this paper we concentrate on the case when γc = 3 and study some basic properties of 3cvc graphs, especially with respect to connectivity, and then present three new infinite families of 3cvc graphs.
