On graphs with no proper perfect dominating set

Abstract

A set of vertices in a graph is perfect dominating if every vertex outside the set is adjacent to exactly one vertex in the set, and is neighborhood connected if the subgraph induced by its open neighborhood is connected. In any graph the full set of vertices is perfect dominating, and in every connected graph the full set of vertices is neighborhood connected. It is shown that(i) in a connected graph, if the only neighborhood connected perfect dominating set is the full set of vertices, then the full set of vertices is also the only perfect dominating set; and (ii) if $ r \ge 3 $ and $ n_1, \ldots ,n_r \ge 2 $, then in $K_{n_1,\ldots,n_r}$ the only perfect dominating set is the full set of vertices. Also, (iii) estimates are derived of how many edges can be removed from or added to $K_{n_1,\ldots ,n_r}$ while preserving the property described in (ii).