Neighborhood Connected Domatic Number of a Graph

Abstract

Let $G=(V,E)$ be a connected graph. A dominating set $S$ of $G$ is called a $neighborhoodconnecteddominatingset$ ($ncd-set$) if the induced subgraph $⟨N(S)⟩$ is connected, where $N(S)$ is the open neighborhood of $S$. A partition $\{V_1,V_2,\dots ,V_k\}$ of $V(G)$, in which each $V_i$ is an ncd-set in $G$, is called a $neighborhoodconnecteddomaticpartition$ or simply $nc-domaticpartition$ of $G$. The maximum order of an nc-domatic partition of $G$ is called the neighborhood connected domatic number (nc-domatic number) of $G$ and is denoted by $d_{nc}(G)$. In this paper, we initiate a study of this parameter.