Neighborhood Connected 2-Domination Number and Connectivity of Graphs

Abstract

A subset of is called a dominating set in if every vertex in  is adjacent to at least one vertex in . A set is called the neighborhood connected 2-dominating set (nc2d-set) of a graph  if every vertex in  is adjacent to at least two vertices in and the induced subgraph is connected. The minimum cardinality of a nc2d-set of  is called the neighborhood connected 2-domination number of and is denoted by . The connectivity  of a graph 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 neighborhood connected 2-domination number and connectivity of a graph and characterize the corresponding extremal graphs.