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

展开
  • 1. 东华理工大学理学院, 江西南昌 330013
    2. 厦门理工学院应用数学学院, 福建厦门 361024
郝国亮, E-mail: guoliang-hao@163.com

收稿日期: 2021-05-24

  网络出版日期: 2024-12-20

基金资助

国家自然科学基金(12061007);国家自然科学基金(11861011)

版权

运筹学学报编辑部, 2024, 版权所有,未经授权。

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

Expand
  • 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 date: 2021-05-24

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization

摘要

$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-彩虹控制数的上下界[J]. 运筹学学报, 2024 , 28(4) : 117 -122 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.011

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.

参考文献

1 Bre?ar B , Henning M A , Rall D F . Rainbow domination in graphs[J]. Taiwanese Journal of Mathematics, 2008, 12 (6): 213- 225.
2 Gao Z , Lei H , Wang K . Rainbow domination numbers of generalized Petersen graphs[J]. Applied Mathematics and Computation, 2020, 382, 125341.
3 Wang Y , Wu X , Dehgardi N , et al. $k$-rainbow domination number of $P_3\square P_n $[J]. Mathematics, 2019, 7 (2): 203.
4 Bre?ar B , ?umenjak T K . On the 2-rainbow domination in graphs[J]. Discrete Applied Mathematics, 2007, 155, 2394- 2400.
5 Kuzman B . On $k$-rainbow domination in regular graphs[J]. Discrete Applied Mathematics, 2020, 284, 454- 464.
6 Furuya M , Koyanagi M , Yokota M . Upper bound on $3$-rainbow domination in graphs with minimum degree 2[J]. Discrete Optimization, 2018, 29, 45- 76.
7 Abdollahzadeh Ahangar H , Amjadi J , Chellali M , et al. Total 2-rainbow domination numbers in trees[J]. Discussiones Mathematicae Graph Theory, 2021, 41 (2): 345- 364.
8 Abdollahzadeh Ahangar H , Khaibari M , Jarfari Rad N , et al. Graphs with large total 2-rainbow domination number[J]. Iranian Journal of Science and Technology Transaction A-Science, 2018, 42, 841- 846.
9 Abdollahzadeh Ahangar H , Amjadi J , Jarfarirad N , et al. Total $k$-rainbow domination numbers in graphs[J]. Communications in Combinatorics and Optimization, 2018, 3 (1): 37- 50.
10 Amjadi J , Dehgardi N , Mohammadi N , et al. Independent 2-rainbow domination in trees[J]. Asian-European Journal of Mathematics, 2015, 8 (2): 1550035.
11 Falahat M , Sheikholeslami S M , Volkmann L . New bounds on the rainbow domination subdivision number[J]. Filomat, 2014, 28 (3): 615- 622.
文章导航

/