Graphs with large restrained domination number (Q1292850): Difference between revisions

A restrained dominating set of a graph \(G=(V,E)\) was defined by \textit{G. S. Domke} et al. [Discrete Math. 203, No. 1-3, 61-69 (1999)] as a set \(S\subseteq V\) such that each vertex in \(V\setminus S\) has a neighbour in \(S\) and a neighbour in \(V\setminus S\). Thus \(V\) is always a restrained dominating set, and we can ask for the minimum cardinality \(\gamma_r(G)\) of a restrained dominating set of \(G\). Since all vertices in \(V\setminus S\) have degree at least two, the existence of degree-one vertices forces a high value of \(\gamma_r\) (e.g. \(\gamma_r(K_{1, n-1}) = n\)), so an interesting upper bound can only be expected in the class of graphs with minimum degree \(\delta(G)\geq 2\). Also, since \(\gamma_r\) is additive on connected components, it is reasonable to consider only connected graphs. For these graphs Domke et al. proved that apart from eight exceptional graphs an upper bound of \(\gamma_r(n)\leq{1\over 2}(n-1)\) holds. In this paper the author now classifies the graphs for which equality holds, obtaining another list of exceptional graphs with some infinite classes.