Roman {3}-domination (double Italian domination)
Roman {3}-domination (double Italian domination)
复制标题
罗马{3}-统治（双重意大利统治）
DOI：
10.1016/j.dam.2020.02.001
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
L. Volkmann
中科院分区：
文献类型：
--
作者：
D. Mojdeh;L. Volkmann
图G = (V, E)与V = V (G)和E = E (G),罗马{3}控制函数是一个函数f: V→{0,1,2,3}属性,∑u N G (V)∈f (u)≥3,如果f (V) = 0,和∑u N G (V)∈f (u)≥2,如果f为任何顶点V (V) = 1∈G .罗马{3}的重量控制函数f和f (V) =∑V V (G)∈f (V)和罗马{3}的最低重量控制函数G是罗马{3}统治的G,用γ{3}R (G)。首先对罗马{2}-统治进行了研究，揭示了其与统治、罗马统治、罗马{2}-统治（意大利统治）和双重罗马统治的关系。最后，我们给出了连通图G在G阶上的罗马{3}-支配数的上界，并刻画了达到这个上界的图。最后，我们证明了Roman{3}-控制的相关决策问题是np完全的，即使对于二部图也是如此。
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∈ N G (v) f (u)≥ 3, if f (v)= 0, and∑ u∈ N G (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 γ {R 3}(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 N P-complete, even for bipartite graphs.