The differential and the roman domination number of a graph

By S. Bermudo, H. Fernau, Jose Maria Sigarreta. 2014

60 citations recorded by the source corpus.

Let G = (V,E) be a graph of order n and let B(S) be the set of vertices in V\S that have a neighbor in the vertex set S. The differential of a vertex set S is defined as ∂(S) = |B(S)| - |S| and the maximum value of ∂(S) for any subset S of V is the differential of G. A Roman dominating function of G is a function f : V → {0,1,2} such that every vertex u with f(u) = 0 is adjacent to a vertex v with f(v) = 2. The weight of a Roman dominating function is the value f(V) = ∑uV f(u). The minimum weight of a Roman dominating function of a graph G is the Roman domination number of G, written γR(G). We prove that γR(G) = n - ∂(G) and present several combinatorial, algorithmic and complexity-theoretic consequences thereof.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/31874695410757a8096c84e9b4ad57215b47feef