An extremal problem for edge domination insensitive graphs (Q1099185): Difference between revisions

What is the minimal number E of edges in a connected graph of order p such that deletion of any edge does not change its domination number \(\gamma\) ? This question is almost completely solved in this paper in three different settings as summarized below. When the minimal dominating set is supposed to remain fixed during edge deletion, then \(E=2p-2\) whenever \(\gamma\geq 2\) and \(p\geq 3\gamma -2\), and does not exist otherwise. In the general case if \(\gamma =1\) and \(p\geq 3\) then \(E=3p-6\), while if \(\gamma\geq 2\) then E equals \(p-1,\) p or \(2p-3\) whenever p is less, equal or greater than \(3\gamma\)-1 respectively. Restriction of the problem to 2-connected graphs yields: if \(\gamma =1\) and \(p\geq 3\) then \(E=3p-6\), while for \(\gamma\geq 2\), E equals p, \(p+2\) or 2p-3 whenever p is greater than \(3\gamma\)-3 and respectively less, equal or greater than \(3\gamma +1\). The remaining cases with \(\gamma\geq 2\) and \(p\leq 3\gamma -3\) remain open problems.