Extremal graphs domination insensitive to the removal of \(k\) edges (Q686272)

The domination number \(\gamma(G)\) of a graph \(G\) is the minimum number of vertices of a dominating set in \(G\), i.e. a subset \(D\) of the vertex set \(V(G)\) of \(G\) such that for each \(x \in V(G)-D\) there exists \(y \in D\) adjacent to \(x\). A graph \(G\) is called \(\gamma_ k\)-insensitive, if \(\gamma(G)\) remains the same after removing arbitrary \(k\) edges from \(G\). The minimum number of edges of a \(\gamma_ k\)-insensitive graph with \(p\) vertices and the domatic number \(\gamma\) is denoted by \(E^ k(p,\gamma)\). For \(k=1\) this number was determined in a previous paper of two of the authors of this paper. In the present paper the exact value is determined for \(E^ k(p,1)\) and lower and upper bounds are given for \(E^ k(p,\gamma)\) in general. In the case \(k+1\leq \gamma \leq 2k\) the value of \(E^ k(p,\gamma)\) is proved to be asymptotically equal to \((k+3)p/2\). Some properties of \(\gamma_ k\)-insensitive graphs are described.