Reliability analyses of regular graphs based on edge-structure connectivity

被引:0
|
作者
Wang, Na [1 ,2 ]
Meng, Jixiang [1 ]
Tian, Yingzhi [1 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[2] Xinjiang Teachers Coll, Sch Math & Sci, Urumqi 830043, Xinjiang, Peoples R China
关键词
Reliability; Disjoint-structure edge-connectivity; Disjoint-substructure edge-connectivity; Hypercube-like graphs; Cayley graphs; Transposition trees; FAULT-TOLERANCE; SUBSTRUCTURE CONNECTIVITY; TOPOLOGICAL PROPERTIES; EXTRACONNECTIVITY; NETWORKS;
D O I
10.1016/j.dam.2024.06.023
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph and F be a connected subgraph of G except for K 1 . Let F = { F 1 , F 2 , ... , F k } be a set of subgraphs of G such that each member of F is isomorphic to F . The F -(disjoint) -structure edge -connectivity is the minimum cardinality of F such that E ( F )'s removal will disconnect G . If every member of F is isomorphic to a connected subgraph of F , then F -(disjoint) -substructure edge -connectivity is defined similarly. In this paper, we determine the star -(disjoint) -substructure edge -connectivity and star -structure edge -connectivity of an n -regular graph G , and give an upper bound on the star -disjoint -structure edge -connectivity of an n -regular graph G . We derive the F -(disjoint) -substructure edge -connectivity of hypercube-like graphs HL n and Cayley graphs generated by transposition trees Gamma n (except for star graphs S n ) for F being C 4 and P 4 , and show a lower bound on the F -(disjoint) -structure edge -connectivity of HL n and Gamma n (except for S n ) for F being C 4 and P 4 . As applications, we determine the F(disjoint) -structure edge -connectivity of crossed cubes CQ n and bubble -sort graphs B n for F being C 4 and P 4 , respectively. Furthermore, we obtain the F -(disjoint)-(sub)structure edge -connectivity of S n for F being C 6 and P 6 . (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
引用
收藏
页码:329 / 342
页数:14
相关论文
共 50 条
  • [21] Sharp spectral bounds for the edge-connectivity of regular graphs
    Suil, O.
    Park, Jeong Rye
    Park, Jongyook
    Zhang, Wenqian
    EUROPEAN JOURNAL OF COMBINATORICS, 2023, 110
  • [22] k-factors in regular graphs and edge-connectivity
    Kimura, Kenji
    Aldred, R.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2008, 5 (01) : 61 - 71
  • [23] Super restricted edge connectivity of regular graphs with two orbits
    Lin, Huiqiu
    Meng, Jixiang
    Yang, Weihua
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (12) : 6656 - 6660
  • [24] Edge-fault-tolerant strong Menger edge connectivity on regular graphs
    Xu, Min
    Li, Pingshan
    THEORETICAL COMPUTER SCIENCE, 2020, 847 : 39 - 48
  • [25] Edge fault tolerance of regular graphs on super 3-restricted edge connectivity
    Wang, Shiying
    Zhang, Guozhen
    ARS COMBINATORIA, 2019, 144 : 55 - 80
  • [26] Reliability Evaluation of Star Graphs in Terms of Extra Edge Connectivity
    Yang, Ming-Chien
    2016 15TH INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED COMPUTING (ISPDC), 2016, : 416 - 419
  • [27] The Edge-Connectivity of Strongly 3-Walk-Regular Graphs
    Feng, Rongquan
    Zhang, Wenqian
    GRAPHS AND COMBINATORICS, 2020, 36 (01) : 115 - 124
  • [28] On 3-restricted edge connectivity of regular Cartesian product graphs
    Wang, Jingyu
    INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS & STATISTICS, 2011, 20 (M11): : 139 - 143
  • [29] Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
    Wang, M
    Li, Q
    DISCRETE MATHEMATICS, 2002, 258 (1-3) : 205 - 214
  • [30] Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
    Yulai Ma
    Davide Mattiolo
    Eckhard Steffen
    Isaak H. Wolf
    Combinatorica, 2024, 44 : 429 - 440