JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2025, Vol. 60 ›› Issue (12): 156-160.doi: 10.6040/j.issn.1671-9352.0.2023.462

Previous Articles     Next Articles

S-T reconstruction of graph based on connectivity optimization

LYU Zhen, WEI Zongtian*   

  1. Department of Mathematics, Xian University of Architecture and Technology, Xian 710055, Shaanxi, China
  • Published:2025-12-10

PDF (PC)

26

Abstract: The concept of subversion strategy and the S-T reconstruction of graphs is proposed, the problem of S-T reconstruction of graph based on connectivity optimization is discussed. A class of overlap graph with special structure is constructed, the optimal reconstruction problem of the overlap of two complete graphs based on connectivity optimization is solved.

Key words: subversion strategy, overlap graph, graph reconstruction, connectivity optimization

CLC Number: 

  • O157
[1] CASABLANCA R M, DANKELMANN P, GODDARD W, et al. The maximum average connectivity among all orientations of a graph[J]. Journal of Combinatorial Optimization, 2021, 43(3):1-28.
[2] HENNING A M, OELLERMANN R O. The average connectivity of a digraph[J]. Discrete Applied Mathematics, 2003, 140(1):143-153.
[3] KIM J, SUIL O. Average connectivity and average edge-connectivity in graphs[J]. Discrete Mathematics, 2013, 313(20):2232-2238.
[4] BEINEKE W L, OELLERMANN R O, PIPPERT R E. The average connectivity of a graph[J]. Discrete Mathematics, 2002, 252(1/2/3):31-45.
[5] SPINOZA H, WEST B D. Reconstruction from the deck of k-vertex induced subgraphs[J]. Journal of Graph Theory, 2019, 90(4):497-522.
[6] MONTEALEGRE P, PEREZ-SALAZAR S, RAPAPORT I, et al. Graph reconstruction in the congested clique[J]. Journal of Computer and System Sciences, 2020, 113:1-17.
[7] OLIVEIRA C I, THATTE D B. An algebraic formulation of the graph reconstruction conjecture[J]. Journal of Graph Theory, 2016, 81(4):351-363.
[8] BONDY J A, MURTY U S R. Graph theory[M]. London: Springer London, 2008.
[9] WHITNEY H. Non-separable and planar graphs[J]. Proceedings of the National Academy of Sciences of the United States of America, 1931, 17(2):125-127.
[1] 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] PANG Guan-song, ZHANG Li-sha, JIANG Sheng-yi*, KUANG Li-min, WU Mei-ling. A multi-level clustering approach based on noun phrases for search results[J]. J4, 2010, 45(7): 39 -44 .
[2] WANG Dun-Xin. Some conditions for finite groups to be solvable[J]. J4, 2009, 44(8): 35 -38 .
[3] DONG Xin-mei . The average order and mean value estimates ofthe error term of function δrk(n)[J]. J4, 2006, 41(5): 91 -94 .
[4] ZHANG Ya-dong1, LI Xin-xiang2, SHI Dong-yang3. Superconvergence analysis of a nonconforming finite element for #br# strongly damped wave equations[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 28 -35 .
[5] CHEN Ya-juan1,2, SHANG Xin-chun1*. Dynamical formation and growth of cavity in a heated viscoelastic sphere[J]. J4, 2013, 48(4): 72 -76 .
[6] YAN Ting-ting, LIU Zhong-kui. Coresolution dimensions[J]. J4, 2013, 48(8): 5 -14 .
[7] PAN Zhen-kuan,WEI Wei-bo,ZHANG Hai-tao . Variational models for image diffusion based on gradient and Laplacian[J]. J4, 2008, 43(11): 11 -16 .
[8] YANG Bi-Cheng. A Hilbert-type integral inequality with the homogeneous kernel of degree zero[J]. J4, 2010, 45(2): 103 -106 .
[9] MU De-yu. A research of screening of salt-tolerance of 12 elm clones in vitro culture[J]. J4, 2013, 48(3): 19 -23 .
[10] LIU Ni. On (P,Q) outer generalized inverse in Hilbert space#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 90 -94 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd