Repositori URV

Identificador: imarina:9150984

Handle: https://hdl.handle.net/20.500.11797/imarina9150984

Autors:
Cabrera Martinez, ARodriguez-Velazquez, J A

Resum:
Let G be a graph of order n(G) and vertex set V(G). Given a set S subset of 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 partial differential partial derivative(p)(S) = vertical bar N-p(S)vertical bar - vertical bar S vertical bar. In this paper, we introduce the study of the perfect differential of a graph, which we define as partial derivative(p)(G) = max{partial derivative(p)(S): S subset of V(G)}. Among other results, we obtain general bounds on partial derivative(p)(G) and we prove a Gallai-type theorem, which states that partial differential partial derivative(p)(G) + gamma(p)(R)(G) = n(G), where gamma(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