English

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (4): 117-122.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.011

•   • 上一篇    下一篇

图的2-彩虹控制数的上下界

谢智红1, 郝国亮1,*(), 庄蔚2   

  1. 1. 东华理工大学理学院, 江西南昌 330013
    2. 厦门理工学院应用数学学院, 福建厦门 361024
  • 收稿日期:2021-05-24 出版日期:2024-12-15 发布日期:2024-12-20
  • 通讯作者: 郝国亮 E-mail:guoliang-hao@163.com
  • 基金资助:
    国家自然科学基金(12061007);国家自然科学基金(11861011)

Lower and upper bounds on the 2-rainbow domination number of a graph

Zhihong XIE1, Guoliang HAO1,*(), Wei ZHUANG2   

  1. 1. College of Science, East China University of Technology, Nanchang 330013, Jiangxi, China
    2. School of Applied Mathematics, Xiamen University of Technology, Xiamen 361024, Fujian, China
  • Received:2021-05-24 Online:2024-12-15 Published:2024-12-20
  • Contact: Guoliang HAO E-mail:guoliang-hao@163.com

RichHTML

2

PDF

69

摘要：

图$G$的$2$-彩虹控制函数定义为从$G$的顶点集$V(G)$到集合$\{1,2\}$的幂集的函数$f$使得对任意满足$f(v)=\varnothing$的顶点$v$, 均有$\bigcup_{u\in N(v)}f(u)=\{1,2\}$成立, 其中$N(v)$是顶点$v$的邻域。称$\sum_{v\in V(G)}|f(v)|$是图$G$的$2$-彩虹控制函数$f$的权。图$G$的$2$-彩虹控制数是指$G$的$2$-彩虹控制函数的最小权。通过对图的结构分析, 利用图的顶点数、周长、围长以及最小度得到了图的$2$-彩虹控制数的一些新的上下界。

关键词: 2-彩虹控制数, 周长, 围长

Abstract:

A $2$-rainbow dominating function of a graph $G$ is a function $f$ from the vertex set $V(G) $ of $G $ to the power set of the set $\{1,2\} $ such that any vertex $v$ with $f(v)=\varnothing$ satisfies that $\bigcup_{u\in N(v)}f(u)=\{1,2\} $, where $N(v) $ is the neighborhood of $v$. The value $\sum_{v\in V(G)}|f(v)| $ is called the weight of a $2$-rainbow dominating function $f $ of $G$. The $2$-rainbow domination number of $G $ is the minimum weight of a $2$-rainbow dominating function of $G$. By the structure analysis of graphs, some new lower and upper bounds on 2-rainbow domination number of graphs are derived in terms of the number of vertices, circumference, girth and minimum degree.

Key words: 2-rainbow domination number, circumference, girth

中图分类号: