On the perfect differential of a graph
Abel Cabrera Martínez, Juan Alberto Rodriguez-Velazquez · Quaestiones Mathematicae · 2021
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 Np(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) = |Np(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) + γpR(G) = n(G), where γpR(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].