Authors: M. Blidia, A. Bouchou, M. Chellali Title: Extremal graphs foe a bound on the Roman domination number Source: Discussiones Mathematicae Graph Theory Received 11.12.2017, Revised 24.04.2018, Accepted 24.04.2018, doi: 10.7151/dmgt.2142 | |
Abstract: 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.
| |
Keywords: Roman domination, Roman domination number, Nordhaus-Gaddum inequalities | |
Links: |