j-Multiple, k-Component Order Neighbor Connectivity

Consider a network modeled by a graph G on n nodes and e edges. There exist several parameters to determine the vulnerability of G. One such parameter is the domination number, which measures the minimum number of nodes necessary in a set so that its closed neighborhood is the entire graph. Multiple domination, sometimes referred to as j-domination, is a variety of domination that requires every node to either be in the set or adjacent to at least j nodes from it. The vulnerability parameter k-component order neighbor connectivity is an extension of domination and is defined as the minimum number of nodes that when removed along with their neighbors leave only components of order less than k. The new parameter, j-multiple, k-component order neighbor connectivity, denoted \(\kappa _{nc,j}^{(k)}\), extends both concepts and is defined as the minimum number of nodes that need to be removed, along with their neighbors, such that the surviving subgraph contains only components of order at most k and every node outside of the set that is adjacent to it is adjacent to at least j nodes from it. The complexity of computing the value for this parameter is NP-hard since it coincides with j-domination when k is 1. Here we introduce this new parameter, establish its bounds, and compare it to several other previously established parameters. We also establish formulas for \(\kappa _{nc,j}^{(k)}\) for several classes of graphs, including complete and complete bipartite graphs as well as paths, cycles, wheels, and complete grid graphs.