An extremal problem for edge domination insensitive graphs

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: An extremal problem for edge domination insensitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099185)