图的双罗马控制数的界

定义在图G的顶点集V(G)上的函数f:V(G)→{0,1,2,3}称为G的双罗马控制函数,如果每个赋值为0的顶点至少与一个赋值为3或两个赋值为2的顶点相邻,并且每个赋值为1的顶点至少与一个赋值为2或3的顶点相邻。图的双罗马控制函数的权为所有顶点的赋值之和。双罗马控制函数的最小权称为双罗马控制数。利用顶点数、围长、周长以及最小度得到了含圈图的双罗马控制数的若干上下界。

Bounds on the double Roman domination number of graphs

A function f:V(G)→{0,1,2,3}defined on the vertex set V(G)of a graph G is called a double Roman dominating function if any vertex assigned 0 is adjacent to at least one vertex assigned 3 or two vertices assigned 2, and any vertex assigned 1 is adjacent to at least one vertex assigned 2 or 3. The weight of a double Roman dominating function is the sum of assigned values of all vertices. The double Roman domination number of a graph G is defined as the minimum weight of a double Roman dominating function on G. Using the number of vertices, girth, circumference and minimum degree of graphs, some lower and upper bounds on the double Roman domination number of graphs with a cycle are established.