An extremal problem for edge domination insensitive graphs
type: Item
instance of: scholarly article
title: An extremal problem for edge domination insensitive graphs
zbMATH Open document ID: 0638.05031
DOI: 10.1016/0166-218X(88)90058-3
author: Ronald D. Dutton
author: Robert Brigham
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4039942
zbMATH Keywords: edge minimal graph
zbMATH Keywords: domination number
zbMATH Keywords: dominating set
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: Domination alteration sets in graphs
cites work: Vertex domination-critical graphs
cites work: Q4163262
cites work: Q3933018
cites work: Domination critical graphs
full work available at URL: 0166-218x(88)90058-3
OpenAlex ID: W2071361850
description: scientific article; zbMATH DE number 4039942