超限制边连通笛卡尔乘积图的边容错性

doi:10.3969/j.issn.0253-2778.2014.12.001

中国科学技术大学学报 ›› 2014, Vol. 44 ›› Issue (12): 967-974.DOI: 10.3969/j.issn.0253-2778.2014.12.001

• 论著 •

超限制边连通笛卡尔乘积图的边容错性

洪振木，徐俊明

中国科学技术大学数学科学学院;中国科学院吴文俊数学重点实验室,安徽合肥 230026

收稿日期:2013-12-12 修回日期:2014-03-19 接受日期:2014-03-19 出版日期:2014-03-19 发布日期:2014-03-19

Edge fault-tolerance of super restricted edge-connected Cartesian product graphs

HONG Zhenmu, XU Junming

School of Mathematical Sciences, University of Science and Technology of China; Wu Wentsun Key Laboratory of Mathematics, USTC, Chinese Academy of Sciences, Hefei 230026, China

Received:2013-12-12 Revised:2014-03-19 Accepted:2014-03-19 Online:2014-03-19 Published:2014-03-19
Contact: XU Junming
About author:HONG Zhenmu, male, born in 1987, PhD candidate. Research field: combinatorics and graph theory.
Supported by:
Supported by NSFC (61272008).

摘要/Abstract

摘要： 如果G-F不连通且每个连通分支至少含有两个顶点，则连通图G的边子集F称为限制边割.如果图G的每个最小限制边割都孤立G中的一条边,则称G是超限制边连通的(简称超λ′).对于满足|F|≤m的任意子集FE(G),超λ′图G的边容错性ρ′(G)是使得G-F仍是超λ′的最大整数m.这里给出了

关键词: 图, 连通度, 容错性, 超限制边连通, 笛卡尔乘积, 正则图, 网络

Abstract: A subset F of edges in a connected graph G is a restricted edge-cut if G-F is disconnected and every component has at least two vertices. A graph G is super restricted edge-connected (super-λ′ for short) if every minimum restricted edge-cut of G isolates at least one edge. The edge fault-tolerance ρ′(G) of a super-λ′ graph G is the maximum integer m for which G-F is still super-λ′ for any subset FE(G) with |F|≤m. It was shown that

Key words: graphs, connectivity, fault tolerance, super restricted edge-connected, Cartesian product, regular graphs, networks

中图分类号:

洪振木，徐俊明. 超限制边连通笛卡尔乘积图的边容错性[J]. 中国科学技术大学学报, 2014, 44(12): 967-974.

HONG Zhenmu, XU Junming. Edge fault-tolerance of super restricted edge-connected Cartesian product graphs[J]. Journal of University of Science and Technology of China, 2014, 44(12): 967-974.

[1]	周宗权, 李传锋. 面向远程量子通信的量子中继与量子U盘[J]. 中国科学技术大学学报, 2021, 51(9): 647-653.
[2]	盖伟, 胡杰. 网络向量自回归模型在波动性溢出分析中的应用[J]. 中国科学技术大学学报, 2021, 51(6): 468-474.
[3]	梁启鹏, 朱巧慧, 康宇, 赵云波. 基于估计的无线网络化控制系统逼近控制策略[J]. 中国科学技术大学学报, 2021, 51(4): 327-334.
[4]	王宁, 席茂, 周文罡, 李礼, 李厚强. 深度视觉目标跟踪进展综述[J]. 中国科学技术大学学报, 2021, 51(4): 335-344.
[5]	李心田, 刘世平. Amply regular图的林-陆-丘曲率和直径[J]. 中国科学技术大学学报, 2021, 51(12): 889-893.
[6]	魏俣童, 鲍秉坤, 张子祺, 朱进. 不稳定传输中受损视频的低延迟修复方法[J]. 中国科学技术大学学报, 2021, 51(10): 717-724.
[7]	刘森, 张直政, 俞涛, 陈志波. 基于网格流的视频修补网络[J]. 中国科学技术大学学报, 2021, 51(1): 1-11.
[8]	胡心颖, 何钰, 孙广中. 基于概率图模型的计算机课程教学认知诊断框架[J]. 中国科学技术大学学报, 2021, 51(1): 12-21.
[9]	朱巧慧, 梁启鹏, 康宇, 赵云波. 无界DoS攻击下网络控制系统的多路径切换保护[J]. 中国科学技术大学学报, 2021, 51(1): 22-32.
[10]	张文静，班志杰. 基于全局的引文网络影响力最大化算法[J]. 中国科学技术大学学报, 2020, 50(8): 1058-1063.
[11]	陶陶，柏建树，刘恒，侯书东，郑啸. 基于WGAN反馈的深度学习差分隐私保护方法[J]. 中国科学技术大学学报, 2020, 50(8): 1064-1071.
[12]	崔文泉，王青芳. 基于双编码器利用在线社交网络信息的股票价格预测[J]. 中国科学技术大学学报, 2020, 50(8): 1093-1101.
[13]	孙磊，张义宁，薛艳芳，乔立山，张丽梅. 自适应功能连接网络学习及其在脑疾病识别中的应用[J]. 中国科学技术大学学报, 2020, 50(8): 1102-1109.
[14]	陈丽芳，王荣杰，刘云庆，周旭. XmR控制图的异常点检测算法研究[J]. 中国科学技术大学学报, 2020, 50(8): 1110-1115.
[15]	白江波，杨阳，张文生. 基于改进CycleGAN的合成孔径雷达图像仿真[J]. 中国科学技术大学学报, 2020, 50(8): 1181-1186.

超限制边连通笛卡尔乘积图的边容错性

Edge fault-tolerance of super restricted edge-connected Cartesian product graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价