Bounds on the order of connected domination vertex critical graphs

Abstract

A vertex subset D of G is a dominating set of G if every vertex in V(G)-D is adjacent to a vertex in D. Moreover, a dominating set D of G is a connected dominating set if G[D] is connected. The minimum cardinality of a connected dominating set of G is called the connected domination number of G and is denoted by yc(G). A graph G is said to be fc-yc-vertex critical if yc(G) = k and yc(G-v) < k for any vertex v of G. In this paper, we establish the order of k-yc-vertex critical graphs in terms of k and the maximum degree A. We prove that a Jt-yc.-vertexcritical graph has A + k<n< (A-l)(k-l) + 3 vertices. Further, the upper bound is sharp for all integers k > 3 when A is even. It has been proved that every k-yc-vertex critical graph achieving the upper bound is A-regular for k = 2 or 3. For k = 4, we prove that every 4-yc-vertex critical graph achieving the upper bound is A-regular. We further show that, for k = 2,3 or 4, there exists a Jt-yc-vertex critical graph of order (A-l)(fc-l) + 3 if and only if A is even. We characterize, for k > 5, that every k-yc-vertex critical graph of order A + k is isomorphic to the cycle of length k + 2.