Menu
A connected graph \(G\) is \((\gamma, k)\)-insensitive if the domination number \(\gamma(G)\) is unchanged when an arbitrary set of \(k\) edges is removed. The problem of finding the least number of edges in any such graph has been solved for \(k = 1\) and for \(k = \gamma(G) = 2\). Asymptotic results as \(n\) approaches infinity are known for \(k \geq 2\) and \(k+1 \leq \gamma(G) \leq 2k\). Note that for \(k = 2\), this bound holds only for graphs \(G$ with \(\gamma(G) \in \{3,4\}\). In this paper, we present an asymptotic bound for the minimum number of edges in an extremal \((\gamma, k)\)-insensitive graph \(G\), where \(k = 2\) and \(n \geq 3\gamma(G)^2 – 2\gamma(G) + 3\) that holds for \(\gamma(G) \geq 3\). For small \(n\), we present tighter bounds (in some cases exact values) for this minimum number of edges.