DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • Roman {3}-domination (doubl...
    Mojdeh, Doost Ali; Volkmann, Lutz

    Discrete Applied Mathematics, 09/2020, Letnik: 283
    Journal Article

    For a graph G=(V,E) with V=V(G) and E=E(G), a Roman {3}-dominating function is a function f:V→{0,1,2,3} having the property that ∑u∈NG(v)f(u)≥3, if f(v)=0, and ∑u∈NG(v)f(u)≥2, if f(v)=1 for any vertex v∈G. The weight of a Roman {3}-dominating function f is the sum f(V)=∑v∈V(G)f(v) and the minimum weight of a Roman {3}-dominating function on G is the Roman {3}-domination number of G, denoted by γ{R3}(G). We initiate the study of Roman {3}-domination and show its relationship to domination, Roman domination, Roman {2}-domination (Italian domination) and double Roman domination. Finally, we present an upper bound on the Roman {3}-domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we show that associated decision problem for Roman {3}-domination is NP-complete, even for bipartite graphs.