图的全局2-彩虹控制数的上界

Upper Bounds on the Global 2-Rainbow Domination Number of Graphs

计算图的全局彩虹控制数的精确值是一个NP完全问题,因此研究图的全局彩虹控制数的界具有重要的理论意义。本文对图的全局彩虹控制数的上界进行研究,通过构造法利用图的直径、围长和最小度等参数得到了直径至少为5或围长至少为6的图的全局2-彩虹控制数的上界。

Calculating the exact values of the global rainbow domination number of graphs is a NP-complete problem,so it is of great theoretical significance to study bounds of the global rainbow domination number of graphs.This paper studies upper bounds on the global rainbow domination number of graphs.By the construction method,we obtain upper bounds of the global 2-rainbow domination number of graphs with the diameter of at least 5 or the girth of at least 6 in terms of the parameters such as the diameter,girth,and minimum degree of graphs.