图与其导出子图的双罗马控制数的研究

Research on the Double Roman Domination Numbers of Graph and Its Induced Subgraphs

摘要: 令图G=(V,E)是简单连通图，V和E分别为图G的顶点集和边集。若函数f:V→{0,1,2,3}满足条件：i)对任意一点v∈V，若f(v)=0，存在v₁,v₂∈N(v)，使得f(v₁)=f(v₂)=2，或存在ω∈N(v)，使得f(ω)=3；ii) 对任意一点v∈V，若f(v)=1，存在ω∈N(v)，使得f(ω)≥2，则称函数f为图G的双罗马控制函数。图G的双罗马控制函数的权值f(V)是图G中各点权值之和，图G的双罗马控制数是图G双罗马控制函数的最小权值，用γ_dR(G)表示。本文主要通过构造的方法证明了，对于任意的正整数a和b，都存在一类图G及其导出子图H，使得γ_dR(G)=a且γ_dR(H)=b。这个结果表明了一个图的双罗马控制数与其导出子图的双罗马控制数之间没有关系。

Abstract: Let G=(V,E) be a connected simple graph with vertex set V and edge set E. If a function f:V→{0,1,2,3} satisfies with the following conditions: i) for ∀v∈V, if f(v)=0, then there exist v₁,v₂∈N(v) such that f(v₁)=f(v₂)=2 or there exist ω∈N(v) such that f(ω)=3; ii) for ∀v∈V, if f(v)=1, then there exist ω∈N(v) such that f(ω)≥2, the function f is called a double Roman dominating function. The weight   of a double Roman dominating function on G is the sum of the weights of all vertices in G, and the minimum weight of a double Roman dominating function on G is the double Roman domination number, denoted by γ_dR(G). In this paper, for any two positive integers a and b, by using the method of constructing, we show that there exist a class of graph G and its induced subgraph H such that γ_dR(G)=a and γ_dR(H)=b. This result shows that there is no relation between the double Roman domination numbers of a graph and its induced subgraphs.