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 \({neighborhood \;connected\; dominating\; set}\) (\({ncd-set}\)) if the induced subgraph \( \langle N(S) \rangle \) is connected, where \( N(S) \) is the open neighborhood of \( S \). A partition \( \{V_1, V_2, \ldots, V_k\} \) of \( V(G) \), in which each \( V_i \) is an ncd-set in \( G \), is called a \({neighborhood\; connected\; domatic\; partition}\) or simply \({nc-domatic \;partition}\) 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.