您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (2): 91-99, 109.doi: 10.6040/j.issn.1671-9352.0.2022.326

•   • 上一篇    下一篇

图的限制性燃烧连通度

薛睿滢(),魏宗田,翟美娟   

  1. 西安建筑科技大学理学院, 陕西 西安 710055
  • 收稿日期:2022-06-10 出版日期:2024-02-20 发布日期:2024-02-20
  • 作者简介:薛睿滢(1997—), 女, 硕士研究生, 研究方向为图论、组合优化及其应用. E-mail: xuery56@163.com
  • 基金资助:
    国家自然科学基金资助项目(61902304)

Restricted burning connectivity of graphs

Ruiying XUE(),Zongtian WEI,Meijuan ZHAI   

  1. School of Science, Xi'an University of Architecture and Technology, Xi'an 710055, Shaanxi, China
  • Received:2022-06-10 Online:2024-02-20 Published:2024-02-20

RichHTML

1

PDF (PC)

355

摘要：

连通度是度量网络抗毁性的一个重要指标, 从图燃烧的角度将该参数推广, 提出图的限制性燃烧连通度概念。在给出若干基本图类的限制性燃烧连通度的基础上, 用数学规划方法研究路的笛卡尔积图、蜘蛛图的限制性燃烧连通度计算问题。通过分析限制性燃烧连通度与图结构的关系, 阐明该参数在刻画网络抗毁性方面的优势。

关键词: 图, 网络抗毁性, 限制性燃烧连通度, 笛卡尔积图, 蜘蛛图, 燃烧数

Abstract:

Connectivity is an important indicator to measure the invulnerability of a network. This parameter is generalized from the perspective of graph burning, and the concept of restricted burning connectivity of graphs is proposed. On the basis of giving some basic graphs' restricted burning connectivity, the restricted burning connectivity calculation problems of the Cartesian product graph of paths and the spider graphs are studied by the mathematical programming method. By analyzing the relationship between restricted burning connectivity and graph structures, the advantages of this parameter in characterizing the invulnerability of networks are clarified.

Key words: graph, network invulnerability, restricted burning connectivity, Cartesian product graph, spider graph, burning number

中图分类号: 

  • O157.5

图1

有2个中心的图G"

图2

舵图H1, 6"

图3

笛卡尔积图Pm□Pn"

图4

蜘蛛图SP(7, 4, 4, 3)"

表1

c∈{0, 1, 2, …, 8}时的参数值与最佳火源"

c(的取值 κbcSP(9, 5, 5, 4)) 最佳火源
0 8 v12
1 7 v12
2 6 v12
3 5 v12
4 4 v12
5 3 v12
6 3 v11或v12
7 2 v11

图5

图G"

表2

几类基本图参数之间的关系"

参数 Pn(n≥3) Cn(n≥3) Km, n(m≥n≥3) H1, n或S1, n-1(n≥3)
κbc(G)与b(G) $\left\{\begin{array}{l}\kappa_b^c(G) \geqslant b(G), c \leqslant\left\lceil\frac{n+1}{2}\right\rceil-\lceil\sqrt{n}\rceil; \\ \kappa_b^c(G) < b(G), c>\left\lceil\frac{n+1}{2}\right\rceil-\lceil\sqrt{n}\rceil。\end{array}\right.$ κbc(G)≥b(G) b(G)≥κbc(G) $\left\{\begin{array}{l}\kappa_b^c(G)=b(G), c=0; \\ \kappa_b^c(G) < b(G), \quad c \geqslant 1。\end{array}\right.$
κbc (G)与κ(G) κbc (G)≥κ(G) κbc (G)≥κ(G) κ(G)≥κbc (G) κbc (G)≥κ(G)
1 BONATO A , JANSSEN J , ROSHANBIN E . How to burn a graph[J]. Internet Mathematics, 2016, 12 (1/2): 85- 100.
2 LIU Huiqing , HU Xuejiao , HU Xiaolan . Burning number of caterpillars[J]. Discrete Applied Mathematics, 2020, 284, 332- 340.
doi: 10.1016/j.dam.2020.03.062
3 BONDY J A , MURTY U S R . Graph theory[M]. London: Springer, 2008.
4 吴漫, 白明丽, 曾咏欣, 等. 基于点割集的最短路径算法的改进与应用[J]. 数学理论与应用, 2018, 38 (3/4): 18- 32.
WU Man , BAI Mingli , ZENG Yongxin , et al. Improvement and application of shortest path algorithm based on point cut sets[J]. Mathematical Theory and Application, 2018, 38 (3/4): 18- 32.
5 魏宗田, 刘勇, 杨威, 等. 网络抗毁性[M]. 西安: 西安交通大学出版社, 2015.
WEI Zongtian , LIU Yong , YANG Wei , et al. Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015.
6 凌捷. 舵图的优美性[J]. 高校应用数学学报A辑(中文版), 1989, 4, 590- 592.
LING Jie . The beauty of rudder diagrams[J]. Journal of Applied Mathematics in Colleges and Universities, Series A (Chinese Edition), 1989, 4, 590- 592.
7 胡雪姣. 几类树的燃烧数[D]. 武汉: 湖北大学, 2020.
HU Xuejiao. Burning numbers of several types of trees[D]. Wuhan: Hubei University, 2020.
[1] 牛泽群,李晓戈,强成宇,韩伟,姚怡,刘洋. 基于图注意力神经网络的实体消歧方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 71-80.
[2] 王静红,吴芝冰,黄鹏,杨家腾,李笔. 基于元路径属性融合的异质网络表示学习[J]. 《山东大学学报(理学版)》, 2024, 59(3): 1-13.
[3] 刘欢,强会英,王洪申,白羽. 树图的2-距离和可区别染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 47-52, 58.
[4] 苏亚男,仝春灵,李勇,苏森原. 广义Petersen图P（n, k）的等全着色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 71-79.
[5] 朱莉,李鹏,王爱法. 单位区间图的半配对k-不相交路覆盖研究[J]. 《山东大学学报(理学版)》, 2024, 59(2): 80-90.
[6] 史雅馨,刘凤霞,蔡华. Wn□Pm的r-hued染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 59-64.
[7] 范金宇,邹杨,熊健,古勇毅. 基于非负CP分解的图像数据监控方法[J]. 《山东大学学报(理学版)》, 2024, 59(1): 27-34.
[8] 那宇嘉,谢珺,杨海洋,续欣莹. 融合上下文的知识图谱补全方法[J]. 《山东大学学报(理学版)》, 2023, 58(9): 71-80.
[9] 李程,车文刚,高盛祥. 一种用于航拍图像的目标检测算法[J]. 《山东大学学报(理学版)》, 2023, 58(9): 59-70.
[10] 高琦,戴洪帅,武艳华. 基于MPEWMA控制图的串联排队网络的监测与控制[J]. 《山东大学学报(理学版)》, 2023, 58(8): 104-110, 117.
[11] 朱利娜,李敬文,孙帅. 几类联图的L(2, 1)-边染色算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(8): 63-72.
[12] 苏宇源,魏宗田,王艳. 图的p-边邻域离散数[J]. 《山东大学学报(理学版)》, 2023, 58(8): 57-62.
[13] 孙情,杨刚. 线性箭图的Gorenstein AC-表示[J]. 《山东大学学报(理学版)》, 2023, 58(8): 48-56.
[14] 尹会玲,陈京荣,苏晓艳. 星图与二部图的某些乘积图上的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2023, 58(6): 18-24, 39.
[15] 常乐,魏宗田. 基于邻域连通度优化的图的N[S]-T重构[J]. 《山东大学学报(理学版)》, 2023, 58(6): 40-45, 76.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 郭文鹃,杨公平*,董晋利. 指纹图像分割方法综述[J]. J4, 2010, 45(7): 94 -101 .
[2] 张雯,张化祥*,李明方,计华. 决策树构建方法:向前两步优于一步[J]. J4, 2010, 45(7): 114 -118 .
[3] 宋 颖,张兴芳,王庆平 . 参数Kleene系统的α-反向三Ⅰ支持算法[J]. J4, 2007, 42(7): 45 -48 .
[4] 郭乔进,丁轶,李宁. 一种基于上下文信息的乳腺肿块ROI检测方法[J]. J4, 2010, 45(7): 70 -75 .
[5] 付海艳,卢昌荆,史开泉 . (F,F-)-规律推理与规律挖掘[J]. J4, 2007, 42(7): 54 -57 .
[6] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
[7] 王碧玉,曹小红*. 算子矩阵的Browder定理的摄动[J]. 山东大学学报（理学版）, 2014, 49(03): 90 -95 .
[8] 胡选子1, 谢存禧2. 基于人工免疫网络的机器人局部路径规划[J]. J4, 2010, 45(7): 122 -126 .
[9] 张京友,张培爱,钟海萍. 进化图论在知识型企业组织结构设计中的应用[J]. J4, 2013, 48(1): 107 -110 .
[10] 肖　华 . 多维反射倒向随机微分方程的解对参数的连续依赖性[J]. J4, 2007, 42(2): 68 -71 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发