(1,2)-PDS in graphs with the small number of vertices of large degrees

Abstract

We define and study a perfect \((1,2)\)-dominating set which is a special case of a \((1,2)\)-dominating set. We discuss the existence of a perfect \((1,2)\)-dominating set in graphs with at most two vertices of maximum degree. In particular, we present a complete solution if the maximum degree equals \(n-1\) or \(n-2\).

Keywords

• domination
• secondary domination
• neighborhoods
• maximum degree