Elimination Properties for Minimal Dominating Sets of Graphs

Abstract

A dominating set of a graph is a vertex subset such that every vertex not in the subset is adjacent to at least one in the subset. In this paper we study whenever there exists a new dominating set contained (respectively, containing) the subset obtained by removing a common vertex from the union of two minimal dominating sets. A complete description of the graphs satisfying such elimination properties is provided.

Keywords

• dominating sets
• elimination properties
• uniform clutters
• 05c69
• 05c65