2-Hamming图的强Menger边连通容错性

解国强; 孟吉翔

doi:10.13568/j.cnki.651094.651316.2023.03.27.0001

您当前的位置：

首页 >

文章列表页 >

2-Hamming图的强Menger边连通容错性

数理科学 | 更新时间：2026-01-21

- 2-Hamming图的强Menger边连通容错性
- 2-Hamming图的强Menger边连通容错性
- 新疆大学学报（自然科学版中英文） 2023年40卷第6期页码：671-675
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  新疆维吾尔自治区自然科学基金“图与网络的容错”（2020D04046）;国家自然科学基金“图的不交路覆盖性及相关问题研究”（12261085）
- DOI：10.13568/j.cnki.651094.651316.2023.03.27.0001
  中图分类号： O157.5
- 纸质出版：2023
- 稿件说明：
移动端阅览
[1]解国强,孟吉翔.2-Hamming图的强Menger边连通容错性[J].新疆大学学报(自然科学版)(中英文),2023,40(06):671-675+682.
[1]解国强,孟吉翔.2-Hamming图的强Menger边连通容错性[J].新疆大学学报(自然科学版)(中英文),2023,40(06):671-675+682. DOI： 10.13568/j.cnki.651094.651316.2023.03.27.0001.

DOI：10.13568/j.cnki.651094.651316.2023.03.27.0001.

摘要

设G是连通图.若G的任一对顶点u

v之间有min{d(u)

d(v)}条边不交的路

则称连通图G为强Menger边连通的.设G是强Menger边连通图

m是非负整数

若对任意满足|F|≤m的边子集F

G-F都是强Menger边连通图

则称G是m-边容错强Menger边连通图.证明了2-Hamming图H(n

2)是(4n-2)-边容错强Menger边连通的

其中n≥2

k≥5.

Abstract

A connected graph G is strongly Menger edge connected if any two of its vertices u

v are connected by min{d(u)

d(v)} edge-disjoint paths. Let G be a strongly Menger edge connected graph and m be a non-negative integer

G is said to be m-edge tolerant strongly Menger edge connected if G-F is strongly Menger edge connected for any edge subset F with |F | ≤ m. It is proved in this paper that the 2-Hamming graphs H(n

2) are(4n-2)-edge fault-tolerant strongly Menger edge connected for n ≥ 2

k ≥ 5.

关键词

Keywords

references

OH E, CHEN J E. On strong Menger-connectivity of star graphs[J]. Discrete Applied Mathematics, 2003, 129(2/3):499-511.

SHIH L M, CHIANG C F, HSU L H, et al. Strong Menger connectivity with conditional faults on the class of hypercube-like networks[J]. Information Processing Letters, 2008, 106(2):64-69.

CHEN Y C, CHEN M H, TAN J J M. Maximally local connectivity and connected components of augmented cubes[J]. Information Sciences, 2014, 273:387-392.

CAI H Y, LIU H Q, LU M. Fault-tolerant maximal local-connectivity on Bubble-sort star graphs[J]. Discrete Applied Mathematics,2015, 181:33-40.

YANG W H, ZHAO S L, ZHANG S R. Strong Menger connectivity with conditional faults of folded hypercubes[J]. Information Processing Letters, 2017, 125:30-34.

LI P S, XU M. Fault-tolerant strong Menger(edge)connectivity and 3-extra edge-connectivity of balanced hypercubes[J]. Theoretical Computer Science, 2018, 707:56-68.

QIAO Y L, YANG W H. Edge disjoint paths in hypercubes and folded hypercubes with conditional faults[J]. Applied Mathematics and Computation, 2017, 294:96-101.

CHENG Q, LI P S, XU M. Conditional(edge-)fault-tolerant strong Menger(edge)connectivity of folded hypercubes[J]. Theoretical Computer Science, 2018, 728:1-8.

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

MENGER K. Zur allgemeinen kurventheorie[J]. Fundamenta Mathematicae, 1927, 10(1):96-115.

FENG K, JI Z J, WEI W. Subnetwork reliability analysis in k-ary n-cubes[J]. Discrete Applied Mathematics, 2019, 267:85-92.

翟登鑫. k-元n-立方体的条件容错强Menger边连通性[J].沈阳大学学报(自然科学版), 2019, 31(2):168-172.

秦学姣.条件故障下3-元n-立方体的容错分析[J].山东科学, 2021, 34(4):114-119.

秦学姣.条件故障下k-元n-立方体的强Menger边连通度[J].西华师范大学学报(自然科学版), 2021, 42(3):268-272.

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

HARARY F. The maximum connectivity of a graph[J]. Proceedings of the National Academy of Sciences, 1962, 48(7):1142-1146.

何中市,杨晓帆,易东.哈拉里图的可靠性分析[J].重庆大学学报(自然科学版), 1996, 19(6):14-19.

WATKINS M E. Connectivity of transitive graphs[J]. Journal of Combinatorial Theory, 1970, 8(1):23-29.

LIU Q H, HUANG X H, ZHANG Z. Restricted edge connectivity of Harary graphs[C]//WANG W F, ZHU X D, DU D Z.Proceedings of the 5th International Conference on Combinatorial Optimization and Applications. Berlin, Heidelberg:SpringerVerlag, 2011.

XU M, LI P S. Edge-fault-tolerant strong Menger edge connectivity on regular graphs[J]. Theoretical Computer Science, 2020,847:39-48.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

暂无数据