(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$.