Optimization and Heuristic Approaches for k-Domination Connectivity

Abstract

Let $G$ be a connected graph. Let $\kappa^{\gamma(k)}(G)$ denote the $k$-domination connectivity. This is defined as the minimum number of vertices whose removal disconnects $G$ so that every resulting component has domination number exactly $k$. This parameter combines the structural robustness of vertex connectivity with domination-based coverage constraints. In this paper, we study structural properties and computational aspects of $\kappa^{\gamma(k)}(G)$. General bounds for the parameter are established. Its behavior is analyzed for several structured graph classes, including trees, grid graphs, corona graphs, and Cartesian product graphs. We also discuss relationships between $\kappa^{\gamma(k)}(G)$ and classical graph parameters such as vertex connectivity and domination number. From the computational perspective, we show that the decision version of the $k$-domination connectivity problem is DP-hard for fixed $k \ge 2$. We formulate the computation of $\kappa^{\gamma(k)}(G)$ as an integer optimization problem. We propose both an exact enumeration algorithm and a heuristic optimization strategy to determine the parameter in general graphs. Our results provide a framework for analyzing domination-based connectivity and help understand how networks can maintain connectivity and monitoring capability under vertex failures.