JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (12): 127-133.doi: 10.6040/j.issn.1671-9352.0.2022.324

•   • Previous Articles     Next Articles

Burning connectivity of oriented graphs

Longmiao XIA(),Zongtian WEI,Liping DING   

  1. Department of Mathematics, Xi'an University of Architecture and Technology, Xi'an 710055, Shaanxi, China
  • Received:2022-05-30 Online:2023-12-20 Published:2023-12-19

RichHTML

2

PDF (PC)

236

Abstract:

The burning number of the graph is combined with the connectivity to propose the concept of burning connectivity of the oriented graphs. Based on the burning connectivity of some special oriented graphs (such as oriented graphs of trees, circles, wheel, etc.), and upper bounds of burning connectivity of cyclic oriented graphs, oriented graphs with a given diameter. An algorithm for computing the burning connectivity of the general oriented graphs is designed, and the complexity of the algorithm is analyzed.

Key words: oriented graph, network invulnerability, burning connectivity, algorithm of burning connectivity

CLC Number: 

  • O157.5

Fig.1

The circulant undirected graph C(8, ±{1, 2, 3}) and their oriented graphs $\vec{C}$ (8, ±{1, 2, 3})"

Fig.2

The algorithm flowchart"

Fig.3

An oriented graphs $\vec{G}$"

1 魏宗田, 刘勇, 杨威, 等. 网络抗毁性[M]. 西安: 西安交通大学出版社, 2015.
WEI Zongtian , LIU Yong , YANG Wei , et al. Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015.
2 BONATO A, JANSSEN J, ROSHANBIN E. Burning a graph as a model of social contagion[C]//International Workshop on Algorithms and Models for the Web-Graph, Cham, Switzerland: Springer, 2014: 13-22.
3 BONATO A , JANSSEN J , ROSHANBIN E . How to burn a graph[J]. Internet Mathematics, 2016, 12 (1): 85- 100.
4 JANSSEN R . The burning number of directed graphs: bounds and computational complexity[J]. Theory and Application of Graphs, 2020, 7 (1): 1- 14.
5 BONDY J A , MURTY U S R . Graph theory[M]. London: Springer, 2008.
6 徐俊明. 图论及其应用[M]. 4版 合肥: 中国科学技术大学出版社, 2018.
XU Junming . Theory and applications of graphs[M]. 4th ed Hefei: University of Science and Technology of China Press, 2018.
7 BOESCH F T , TINDELL A . Circulants and their connectivities[J]. Journal of Graph Theory, 2010, 8, 487- 499.
8 刘振宏, 蔡茂诚. 组合最优化算法和复杂性[M]. 北京: 清华大学出版社, 1988.
LIU Zhenhong , CAI Maocheng . Combinatorial optimization algorithms and complexity[M]. Beijing: Tsinghua University Press, 1988.
[1] WENG Ting-ting, WEI Zong-tian. Weighted neighbor toughness of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 36-43.
[2] CUI Chen, WEI Zong-tian. General p-neighbor integrity of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 72-78.
[3] SHI Ming, WEI Zong-tian, LIU Yong, WENG Ting-ting. Vertex weighted neighbor tenacity of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(5): 26-32.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
[2] 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 .
[3] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[4] SUN Xiao-ting1, JIN Lan2*. Application of DOSY in oligosaccharide mixture analysis[J]. J4, 2013, 48(1): 43 -45 .
[5] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[6] YANG Lun, XU Zheng-gang, WANG Hui*, CHEN Qi-mei, CHEN Wei, HU Yan-xia, SHI Yuan, ZHU Hong-lei, ZENG Yong-qing*. Silence of PID1 gene expression using RNA interference in C2C12 cell line[J]. J4, 2013, 48(1): 36 -42 .
[7] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[8] YANG Ying, JIANG Long*, SUO Xin-li. Choquet integral representation of premium functional and related properties on capacity space[J]. J4, 2013, 48(1): 78 -82 .
[9] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[10] DONG Wei-wei. A new method of DEA efficiency ranking for decision making units with independent subsystems[J]. J4, 2013, 48(1): 89 -92 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd