M. Blidia, A. Bouchou, M. Chellali
Extremal graphs foe a bound on the Roman domination number
Discussiones Mathematicae Graph Theory
Received 11.12.2017, Revised 24.04.2018, Accepted 24.04.2018, doi: 10.7151/dmgt.2142

A Roman dominating function on a graph G=(V,E) is a function f:V(G)->{0,1,2} such that every vertex u for which f(u)=0 is adjacent to at least one vertex v with f(v)=2. The weight of a Roman dominating function is the value w(f)=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G)≤ n+1-Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G)=n+1-Δ is co-\mathcal{NP}% -complet\textrm{e}. Finally, we provide a characterization of extremal graphs of a Nordhaus--Gaddum bound for γR(G)+γR(‾{G}), where ‾{G} is the complement graph of G.

Roman domination, Roman domination number, Nordhaus-Gaddum inequalities