JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (6): 40-45, 76.doi: 10.6040/j.issn.1671-9352.0.2021.454

Previous Articles     Next Articles

Graph N[S]-T reconstruction based on neighbor connectivity optimization

Le CHANG(),Zongtian WEI   

  1. School of Science, Xi'an University of Architecture and Technology, Xi'an 710055, Shaanxi, China
  • Received:2021-06-28 Online:2023-06-20 Published:2023-05-23

RichHTML

1

PDF (PC)

149

Abstract:

Considering the neighbor invulnerability recovery of a damaged network based on the optimization idea, the neighbor subversion strategy and the concept of reconstruction are proposed. The problem of graph reconstruction based on neighbor connectivity optimization is studied. An optimal reconstruction method and an algorithm of Cartesian product graph of two complete graphs under the optimal neighbor subversion strategy are presented.

Key words: neighbor subversion strategy, reconstruction, optimal reconstruction, complete graph, cartesian product graph

CLC Number: 

  • O157.5

Fig.1

(a) Cycle C9, (b) after subversion, (c) the optimal reconstruction of C9"

Fig.2

(a) Tree G, (b) after subversion, (c) an optimal reconstruction of G"

Fig.3

(a) Path P8, (b) after subversion, (c) and (d) two different optimal reconstructions of P8"

Fig.4

Optimal reconstruction of K9×K3"

Fig.5

Optimal reconstruction of K9×K6"

1 COZZENS M B , WU S . Extreme values of the edge-neighbor-connectivity[J]. ARS Combinatoria-Waterloo then Winnipeg-, 1995, 39 (1): 199- 210.
2 GUNTHER G , HATNELL B L . On m-connected and k-neighbor-connected graphs[J]. Graph Theory, Combinatorics and Applications, 1991, 2, 585- 596.
3 TUTTE W T . The reconstruction problem in graph theory[J]. British Polymer Journal, 1977, 9 (3): 180- 183.
doi: 10.1002/pi.4980090302
4 ABDALLAH M , HUNG C N . Neighbor connectivity of the alternating group graph[J]. Journal of Interconnection Networks, 2021, 2150014.
5 SHANG Y J , HAO R X , GU M M . Neighbor connectivity of two kinds of cayley graphs[J]. Acta Mathematicae Applicatae Sinica, English Series, 2018, 34 (2): 386- 397.
doi: 10.1007/s10255-018-0739-9
6 WANG M , LIN Y , WANG S . The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs[J]. Discrete Applied Mathematics, 2017, 246 (9): 108- 118.
7 GUNTHER G . Neighbour-connectivity in regular graphs[J]. Discrete Applied Mathematics, 1985, 11 (3): 233- 243.
8 BONDY J A , MURTY U S R . Graph theory with applications[M]. London: Springer, 2008.
9 魏宗田, 刘勇. 网络抗毁性[M]. 西安: 西安交通大学出版社, 2015.
WEI Zongtian , LIU Yong . Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015.
10 WEI Zongtian , MAI Anchan , ZHAI Meijuan . Vertex-neighbor-scattering number of graphs[J]. ARS Combinatoria: An Australian-Canadian Journal of Combinatorics, 2011, 102, 417- 426.
[1] WANG Ligong, YU Zhiming, ZHOU Feng, TAO Lijie, XING Luqi. Two kinds of integral graphs based on complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 155-159.
[2] WANG Shu-juan, YANG Huo-gen, CHAI Ying. Reconstruction of rational polynomial Coons surface patches throuth Bézier triangular geodesic [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 102-110.
[3] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[4] YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.
[5] ZHANG Sheng-gui, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total coloring and Ⅵ-total coloring of almost complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(5): 23-25.
[6] LIU Jing-shu, WANG Li, LIU Jing-lei. Nyström extension based on circulant matrix projection [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 55-66.
[7] ZHANG Xiao-dong, DONG Wei-guang, TANG Min-an, GUO Jun-feng, LIANG Jin-ping. gOMP reconstruction algorithm based on generalized Jaccard coefficient for compressed sensing [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(11): 23-28.
[8] ZHANG Ben-hui, TANG Yuan-sheng, CHEN Wen-bing. Communication rate in the secret reconstruction phase [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(05): 7-11.
[9] LIU Xin-sheng, DENG Wei-dong, WANG Zhi-qiang. Several conclusions of adjacent vertex distinguishing E-total coloring of the cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 5-8.
[10] FAN Ting-jun, DIAO Jin-mei. Research advances of tissue-engineered human corneal endothelium [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(1): 1-7.
[11] WANG Wen-hua, CAO Huai-xin*, LI Wei. (A,B)-quantum measurements [J]. J4, 2012, 47(4): 70-76.
[12] JIANG Hua, LI Ming-zhen, WANG Xin. A  PPM probabilistic packet marking improving scheme [J]. J4, 2011, 46(9): 85-88.
[13] FAN Ting-jun, MA Xi-ya, ZHAO Jun, HU Xiu-zhong. Establishment of a human corneal endothelial cell strain and in vitro reconstruction of a tissue-engineered  human corneal endothelium [J]. J4, 2011, 46(10): 142-151.
[14] YUAN Xiu-hua. The total signed domination number of complete graph [J]. J4, 2010, 45(8): 43-46.
[15] . Studies on effects of tissue-engineered human corneal endothelia on maintaining corneal transparency of New Zealand white rabbits [J]. J4, 2010, 45(3): 1-5.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] TANG Feng-qin1, BAI Jian-ming2. The precise large deviations for a risk model with extended negatively upper orthant dependent claim  sizes[J]. J4, 2013, 48(1): 100 -106 .
[2] CHENG Zhi1,2, SUN Cui-fang2, WANG Ning1, DU Xian-neng1. On the fibre product of Zn and its property[J]. J4, 2013, 48(2): 15 -19 .
[3] TANG Xiao-hong1, HU Wen-xiao2*, WEI Yan-feng2, JIANG Xi-long2, ZHANG Jing-ying2, SHAO Xue-dong3. Screening and biological characteristics studies of wide wine-making yeasts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 12 -17 .
[4] 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 .
[5] TIAN Xue-gang, WANG Shao-ying. Solutions to the operator equation AXB=C[J]. J4, 2010, 45(6): 74 -80 .
[6] HUO Yu-hong, JI Quan-bao. Synchronization analysis of oscillatory activities in a biological cell system[J]. J4, 2010, 45(6): 105 -110 .
[7] 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 .
[8] LIU Ting-ting, CHEN Zhi-yong, LI Xiao-qin*, YANG Wen-zhi. The Berry-Esseen bound for the sequence of #br# negatively associated random variables#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 101 -106 .
[9] LIU Yan-ping, WU Qun-ying. Almost sure limit theorems for the maximum of Gaussian sequences#br# with optimized weight[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 50 -53 .
[10] 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 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd