Best possible upper bounds on the restrained domination number of cubic graphs

Abstract

A dominating set in a graph is a set of vertices such that every vertex in is adjacent to a vertex in . A restrained dominating set of is a dominating set with the additional restraint that the graph obtained by removing all vertices in is isolate‐free. The domination number and the restrained domination number are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of . Let be a cubic graph of order . A classical result of Reed states that , and this bound is best possible. To determine the best possible upper bound on the restrained domination number of is more challenging, and we prove that .