DOI: 10.1002/jgt.23095 ISSN: 0364-9024

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

Boštjan Brešar, Michael A. Henning
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

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 .

More from our Archive