On the perfect differential of a graph

Abstract

Let G be a graph of order n(G) and vertex set V(G). Given a set S ⊆ V(G), we define the perfect neighbourhood of S as the set N_p (S) of all vertices in V(G)\S having exactly one neighbour in S. The perfect differential of S is defined to be ∂_p (S) = |N_p (S)| − |S|. In this paper, we introduce the study of the perfect differential of a graph, which we define as ∂_p (G) = max{∂_p (S) : S ⊆ V(G)}. Among other results, we obtain general bounds on ∂_p (G) and we prove a Gallai-type theorem, which states that ∂_p (G) + γ^p _R (G) = n(G), where γ^p _R (G) denotes the perfect Roman domination number of G. As a consequence of the study, we show some classes of graphs satisfying a conjecture stated by Bermudo [Discrete Appl. Math. 232 (2017), 64-72].