图的分支点连通度和分支边连通度综述（英文）

刘雪梅; 孟吉翔

doi:10.13568/j.cnki.651094.651316.2023.02.18.0001

您当前的位置：

首页 >

文章列表页 >

图的分支点连通度和分支边连通度综述（英文）

研究精粹 | 更新时间：2026-01-23

- 图的分支点连通度和分支边连通度综述（英文）
- 图的分支点连通度和分支边连通度综述（英文）
- 新疆大学学报（自然科学版中英文） 2023年40卷第3期页码：257-266
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  supported by National Natural Science Foundation of Xingjiang,China “Fault-tolerance of graphs and networks”(2020D04046);National Natural Science Foundation of the People's Republic of China “On the sizes of vertex(edge)-k-maximal r-uniform hypergraphs”(11261086),“On the disjoint path covers in graphs and related problems”(12261085)
- DOI：10.13568/j.cnki.651094.651316.2023.02.18.0001
  中图分类号： O157.5
- 纸质出版：2023
- 稿件说明：
移动端阅览
[1]刘雪梅,孟吉翔.图的分支点连通度和分支边连通度综述（英文）[J].新疆大学学报(自然科学版)(中英文),2023,40(03):257-266+273.
[1]刘雪梅,孟吉翔.图的分支点连通度和分支边连通度综述（英文）[J].新疆大学学报(自然科学版)(中英文),2023,40(03):257-266+273. DOI： 10.13568/j.cnki.651094.651316.2023.02.18.0001.

DOI：10.13568/j.cnki.651094.651316.2023.02.18.0001.

摘要

对简单的非完全图G和任意的正整数h，图G的h分支点连通度（h分支边连通度）是图G顶点子集（边子集）其删除呈现至少h个分支的最小基数.在此综述中，主要总结了一些关于h分支点连通度和h分支边连通度的一般性结论，以及一些熟知网络图的h分支点连通度和h分支边连通度的确切值．

Abstract

For a simple non-complete graph G

the h-component connectivity(resp.

h-component edge connectivity) of G is the minimum cardinality of a vertex subset of G whose deletion renders at least h components for any positive integer h. In this survey

we mainly summarize results on h-component connectivity(resp.

h-component edge connectivity) and the exact values of the h-component connectivity(resp.

h-component edge connectivity) of some well-known networks.

关键词

Keywords

references

BONDY J A, MURTY U S R. Graph Theory[M]. New York:Springer, 2008.

HSU L H, CHENG E, LIPTAK L, et al. Component connectivity of the hypercubes[J]. International Journal of Computer Mathematics, 2012, 89(2):137-145.

CHARTRAND G, KAPOOR S F, LESNIAK L, et al. Generalized connectivity in graphs[J]. Bulletin of the Bombay Mathematical Colloquium, 1984,2:1-6.

SAMPATHKUMAR E. Connectivity of a graph-A generalization[J]. Journal of Combinatorics, Information&System Sciences, 1984, 9:71-78.

OELLERMANN O R. On the l-connectivity of a graph[J]. Graphs and Combinatorics, 1987, 3:285-291.

LI X Y, LIN C K, FAN J X, et al. Relationship between extra connectivity and component connectivity in networks[J]. The Computer Journal, 2021,64(1):38-53.

HAO R X, GU M M, CHANG J M. Relationship between extra edge connectivity and component edge connectivity for regular graphs[J]. Theoretical Computer Science, 2020, 833:41-55.

GUO L T, ZHANG M Z, ZHAI S H, et al. Relation of extra edge connectivity and component edge connectivity for regular networks[J]. International Journal of Foundations of Computer Science, 2021, 32(2):137-149.

LIU J F, ZHOU S M, WANG D J, et al. Component diagnosability in terms of component connectivity of hypercube-based compound networks[J].Journal of Parallel and Distributed Computing, 2022, 162:17-26.

PREPARATA F P, METZE G, CHIEN R T. On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers, 1967, EC-16:848-854.

ZHANG S R, LIANG D Y, CHEN L, et al. The component diagnosability of hypercubes with large-scale faulty nodes[J]. The Computer Journal, 2022,65(5):1129-1143.

TIAN Y C, ZHU Q. r-Component diagnosability of hypercubes under the PMC model[J]. Theoretical Computer Science, 2022, 933:114-124.

DAY D P, OELLERMANN O R, SWART H C. Bounds on the size of graphs of given order and l-connectivity[J]. Discrete Mathematics, 1999,197(1/2/3):217-223.

LI H, ZHANG S M, YE C F, et al. The g-component connectivity of graphs[J]. Theoretical Computer Science, 2021, 889:96-104.

GUO L T, GE J. Note on reliability analysis of Cartesian product of networks for components[J]. Journal of Interconnection Networks, 2021, 21:2142010.

BOSE B, BROEG B, KWON Y, et al. Lee distance and topological properties of k-ary n-cubes[J]. IEEE Transactions on Computers, 1995, 44:1021-1030.

LYU M J, FAN J X, ZHOU J Y, et al. The reliability of k-ary n-cube based on component connectivity[J]. The Computer Journal, 2022, 65(8):2197-2208.

XU L Q, ZHOU S M, HSIEH S Y. An O(log3 N)algorithm for reliability assessment of 3-ary n-cubes based on h-extra edge connectivity[J]. IEEE Transactions on Reliability, 2022, 71(3):1230-1240.

IMRICH W, KLAVZAR S. Product graphs, structure and recognition[M]. New York:John Wiley and Sons, 2000.

YANG Y Y, ZHANG M Z, MENG J X. Fault tolerance analysis for hamming graphs with large-scale faulty links based on k-component edgeconnectivity[J]. Journal of Parallel and Distributed Computing, 2023, 173:107-114.

ZHAO S L, YANG W H, ZHANG S R. Component connectivity of hypercubes[J]. Theoretical Computer Science, 2016, 640:115-118.

ZHAO S L, YANG W H, ZHANG S R, et al. Component edge connectivity of hypercubes[J]. International Journal of Foundations of Computer Science, 2018, 29(6):995-1001.

HUANG K, WU J. Area efficient layout of balanced hypercubes[J]. International Journal of High Speed Electronics and Systems, 1995, 6(4):631-646.

GU M M, CHANG J M, HAO R X. On computing component(edge)connectivities of balanced hypercubes[J]. The Computer Journal, 2020, 63:1311-1320.

BOSSARD A, KANEKO K. Node-to-set disjoint-path routing in hierarchical cubic networks[J]. The Computer Journal, 2012, 55:1440-1446.

XU L Q, GUO L T. Analysis on the component connectivity of enhanced hypercubes[J]. The Computer Journal, 2022, 65(4):890-896.

XU L Q, ZHOU S M, LIU J F, et al. Reliability measure of multiprocessor system based on enhanced hypercubes[J]. Discrete Applied Mathematics,2021, 289:125-138.

LIN S W, ZAHNG H Q. The generalized 4-connectivity of hypercubes[J]. Discrete Applied Mathematics, 2017, 220:60-67.

ZHAO S L, HAO R X, CHENG E. Two kinds of generalized connectivity of dual cubes[J]. Discrete Applied Mathematics, 2019, 257:306-316.

LI T K, TAN J J M, HSU L H, et al. The shuffle-cubes and their generalization[J]. Information Processing Letters, 2011, 77(1):35-41.

DING T T, LI P S, XU M. The component(edge)connectivity of shuffle-cubes[J]. Theoretical Computer Science, 2020, 835:108-119.

MALLUHI Q M, BAYOUMI M A. The hierarchical hypercube:a new interconnection topology for massively parallel systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5:17-30.

VAIDYA A S, RAO A S N, SHANKAR S R. A class of hypercube-like networks[C]//Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing. Dallas:IEEE, 1993.

LIU D, LI P S, ZHANG B C. Component edge connectivity of hypercube-like networks[J]. Theoretical Computer Science, 2022, 911:19-25.

JWO J, LAKSHMIVARAHAN S, DHALL S K. A new class of interconnection networks based on the alternating group[J]. Networks, 1993, 23:315-326.

GU M M, HAO R X, CHANG J M. Measuring the vulnerability of alternating group graphs and split-star networks in terms of component connectivity[J]. IEEE Access, 2019, 7:97745-97759.

GU M M, HAO R X, CHANG J M. Reliability analysis of alternating group graphs and split-stars[J]. The Computer Journal, 2021, 64(9):1425-1436.

CHENG E, LIPMAN M J, PARK H A. An attractive variation of the star graphs:split-stars[J]. Technical Report, 1998, 98:3.

LIN L M, HUANG Y Z, WANG D J, et al. Component reliability evaluation on split-stars[J]. IEEE Access, 2019, 7:147939-147953.

GUO C X, WU H T, TAN K, et al. DCell:a scalable and fault-tolerant network structurre for data centers[J]. Computer Communication Review, 2008,38(4):75-86.

LIU X M, MENG J X, SABIR E. Component connectivity of the data center network DCell[J]. Applied Mathematics and Computation, 2023, 444:127822.

GATES W H, PAPADIMITRIOU C H. Bounds for sorting by prefix reversal[J]. Discrete Mathematics, 1979, 27:47-49.

GU M M, HAO R X, TANG S M, et al. Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs[J]. Discrete Applied Mathematics, 2020, 279:80-91.

CHOU Z T, HSU C C, SHEU J P. Bubble-sort star graphs:a new interconnection network[C]//Proceedings of 1996 International Conference on Parallel and Distributed Systems. Tokyo:IEEE, 1996.

GUO L T, LEE C W. Reliability analysis of the bijective connection networks for components[J]. Mathematics, 2019, 7:546.

CHIANG W K, CHEN R J. The(n, k)-star graphs:a generalized star graph[J]. Information Processing Letters, 1995, 56:259-264.

GUO L T. Reliability analysis of hypercube networks and folded hypercube networks[J]. WSEAS Transactions on Mathematics, 2017, 16:331-338.

ZHAO S L, YANG W H. Conditional connectivity of folded hypercubes[J]. Discrete Applied Mathematics, 2019, 257:388-392.

ZHUANG H B, GUO W Z, LI X Y, et al. The component connectivity, component diagnosability, and t/k-diagnosability of bicube networks[J].Theoretical Computer Science, 2021, 896:145-157.

CHENG E, QIU K, SHEN Z Z. Connectivity results of hierarchical cubic networks as associated with linearly many faults[C]//IEEE 17th International Conference on Computational Science and Engineering. Chengdu:IEEE, 2014.

CHENG E, QIU K, SHEN Z Z. Connectivity results of complete cubic networks as associated with linearly many faults[J]. Journal of Interconnection Networks, 2015, 15:1550007.

CHENG E, QIU K, SHEN Z Z. Structural properties of generalized exchanged hypercubes[M]. New York:Springer, 2017.

ZHANG Q F, XU L Q, YANG W H, et al. Reliability analysis of the generalized exchanged hypercube[J]. Parallel Processing Letters, 2020, 30:2050009.

SHU C, WANG Y, FAN J X, et al. Fault-tolerant routing of generalized hypercubes under 3-component connectivity[C]//IEEE International Conference on Parallel&Distributed Processing with Applications, Big Data&Cloud Computing, Sustainable Computing&Communications, Social Computing&Networking. New York:IEEE, 2021.

FERRERO D, HANUSCH S. Component connectivity of generalized Petersen graphs[J]. International Journal of Computer Mathematics, 2014, 9:1940-1963.

ZHAO S L, CHANG Z M, HAO R X. Reliability assessment of the Cayley graph generated by trees[J]. Discrete Applied Mathematics, 2020, 287:10-14.

GUO L T. Reliability analysis of twisted cubes[J]. Theoretical Computer Science, 2018, 707:96-101.

GUO L T, SU G F, LIN W S, et al. Fault tolerance of locally twisted cubes[J]. Applied Mathematics and Computation, 2018, 334:401-406.

SHANG H, SABIR E, MENG J X, et al. Characterizations of optimal component cuts of locally twisted cubes[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43:2087-2103.

SHANG H, SABIR E, MENG J X. Conditional edge connectivity of the locally twisted cubes[J]. Journal of the Operations Research Society of China,2019, 7:501-509.

ZHOU Q R, ZHOU S M, LIU X Q, et al. Reliability of divide-and-swap cube based on r-component connectivity and diagnosability[J]. Journal of Interconnection Networks, 2022, 22(1):2022.

GUO L T. Component connectivity of crossed cubes[J]. WSEAS Transactions on Mathematics, 2017, 16:290-294.

LIU X Q, ZHOU S M, ZHANG H, et al. The component(edge)connectivity of round matching composition networks[J]. International Journal of Foundations of Computer Science, 2022, 33:1005-1018.

GU M M, CAHNG J M, HAO R X. On component connectivity of hierarchical star networks[J]. International Journal of Foundations of Computer Science, 2020, 31:313-326.

GUO L T. Fault tolerance of bubble-sort networks on components[J]. Journal of Internet Technology, 2021, 22:637-643.

ZHANG Q F, XU L Q, YANG W H. Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edgeconnectivity[J]. Journal of Parallel and Distributed Computing, 2021, 147:124-131.

HUA X H, YNAG L L. Component(edge)connectivity of pancake graphs[J]. Ars Mathematica Contemporanea, 2023, 23:1-13.

CHANG J M, PAI K J, WU R Y, et al. The 4-component connectivity of alternating group networks[J]. Theoretical Computer Science, 2019, 766:38-45.

CHANG J M, PAI K J, YANG J S, et al. Two kinds of generalized 3-connectivities of alternating group networks[C]//12th International Workshop on Frontiers in Algorithmics. Guangzhou:Springer, 2018.

DAY D, OELLERMANN O R, SWART H C. The l-connectivity function of trees and complete multipartite graphs[J]. The Journal of Combinatorial Mathematics and Combinatorial Computing, 1911, 10:183-192.

OELLERMANN O R. A note on the l-connectivity function of a graph[J]. Congressus Numerantium, 1987, 60:181-188.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

超立方体外边连通度可靠性分析(英文)

一类正则图的边坚韧度(英文)

超立方体的r-Hued染色（英文）

关于一些图运算的逆和反度指标