Neighborhood Connected 2-Domination Number and Connectivity of Graphs
Keywords:
Neighborhood connected 2-domination, ConnectivityAbstract
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.