Complementary Connected Domination Number and Connectivity of a Graph

For any graph G=(V,E), a subset S of V is a dominating set if every vertex in V-S is adjacent to at least one vertex in S. A dominating set S is said to be a complementary connected dominating set if the induced subgraph \langle V-S \rangle is connected. The minimum cardinality of a complementary connected dominating set is called the complementary connected domination number and is denoted by gamma_cc(G). The connectivity kappa(G) of a connected graph G is the minimum number of vertices whose removal results in a disconnected or trivial graph. In this paper we find an upper bound for the sum of the complementary connected domination number and connectivity of a graph and characterize the corresponding extremal graphs.