JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (2): 91-99, 109.doi: 10.6040/j.issn.1671-9352.0.2022.326

Previous Articles     Next Articles

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

0

PDF (PC)

97

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

CLC Number: 

  • O157.5

Fig.1

A graph G with two centers"

Fig.2

The helm graph H1, 6"

Fig.3

The Cartesian product graph Pm□Pn"

Fig.4

The spider graph SP(7, 4, 4, 3)"

Table 1

Parameter value and optimal fire source when 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

Fig.5

The graph G"

Table 2

The relationship between the parameters of several basic graphs"

参数 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] NIU Zequn, LI Xiaoge, QIANG Chengyu, HAN Wei, YAO Yi, LIU Yang. Entity disambiguation method based on graph attention networks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 71-80.
[2] WANG Jinghong, WU Zhibing, HUANG Peng, YANG Jiateng, LI Bi. Heterogeneous network representation learning based on metapath attribute fusion [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(3): 1-13.
[3] Yanan SU,Chunling TONG,Yong LI,Senyuan SU. Equitable total coloring of generalized Petersen graphs P(n, k) [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 71-79.
[4] Li ZHU,Peng LI,Aifa WANG. Study on semi-paired k-disjoint path cover of unit interval graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 80-90.
[5] Yaxin SHI,Fengxia LIU,Hua CAI. On r-hued coloring of Wn□Pm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 59-64.
[6] Yujia NA,Jun XIE,Haiyang YANG,Xinying XU. Context fusion-based knowledge graph completion [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(9): 71-80.
[7] Yuyuan SU,Zongtian WEI,Yan WANG. The p-edge neighbor scattering number of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(8): 57-62.
[8] Lina ZHU,Jingwen LI,Shuai SUN. L(2, 1)- edge coloring algorithm for several kinds of composite graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(8): 63-72.
[9] Le CHANG,Zongtian WEI. Graph N[S]-T reconstruction based on neighbor connectivity optimization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 40-45, 76.
[10] Huiling YIN,Jingrong CHEN,Xiaoyan SU. The k-path vertex cover in some products graphs of star graph and bipartite graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 18-24, 39.
[11] Ying JI,Bo DENG,Haixing ZHAO,Yanlong TANG. Domination entropy based on graph operations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 140-150.
[12] Xinsheng WANG,Xiaofei ZHU,Chenghong LI. Label guided multi-scale graph neural network for protein-protein interactions prediction [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 22-30.
[13] Longmiao XIA,Zongtian WEI,Liping DING. Burning connectivity of oriented graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 127-133.
[14] Jin LI,Changqing XU. Adjacent vertex distinguishing edge coloring of IC-planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 134-139.
[15] Linyu LAN,Jingwen LI,Shucheng ZHANG,Lijing ZHANG,Huayu SHEN. Vertex reducibletotal labeling algorithm for graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 135-146.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] GUO Wen-juan, YANG Gong-ping*, DONG Jin-li. A review of fingerprint image segmentation methods[J]. J4, 2010, 45(7): 94 -101 .
[2] ZHANG Wen, ZHANG Hua-xiang*, LI Ming-fang, JI Hua. A decision tree construction approach: two-step forward is better than one[J]. J4, 2010, 45(7): 114 -118 .
[3] SONG Ying,ZHANG Xing-fang ,WANG Qing-ping . α-reverse triple I method in the parametric Kleene's system[J]. J4, 2007, 42(7): 45 -48 .
[4] GUO Qiao-jin, DING Yi, LI Ning. A context based method for ROI detection in digitized mammograms[J]. J4, 2010, 45(7): 70 -75 .
[5] FU Hai-yan,LU Chang-jing,SHI Kai-quan . (F,F-)-law inference and law mining[J]. J4, 2007, 42(7): 54 -57 .
[6] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
[7] WANG Bi-yu, CAO Xiao-hong*. The perturbation for the Browder’s theorem of operator matrix#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 90 -95 .
[8] HU Xuan-zi1, XIE Cun-xi2. A robot local path plan based on artificial immune network[J]. J4, 2010, 45(7): 122 -126 .
[9] ZHANG Jing-you, ZHANG Pei-ai, ZHONG Hai-ping. The application of evolutionary graph theory in the design of knowledge-based enterprises’ organization strucure[J]. J4, 2013, 48(1): 107 -110 .
[10] XIAO Hua . Continuous dependence of the solution of multidimensional reflected backward stochastic differential equations on the parameters[J]. J4, 2007, 42(2): 68 -71 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd