正则图的宽直径

doi:10.3969/j.issn.0253-2778.2013.08.001

中国科学技术大学学报 ›› 2013, Vol. 43 ›› Issue (8): 603-606.DOI: 10.3969/j.issn.0253-2778.2013.08.001

• 原创论文 • 下一篇

正则图的宽直径

李佳傲

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

收稿日期:2012-12-20 修回日期:2013-05-22 出版日期:2013-08-31 发布日期:2013-08-31

The wide-diameter of regular graphs

LI Jiaao

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:2012-12-20 Revised:2013-05-22 Online:2013-08-31 Published:2013-08-31
Contact: XU Junming
About author:LI Jiaao, male, born in 1990, master. Research field: Combinatorics and graph theory. E-mail: lijiaao@mail.ustc.edu.cn

摘要/Abstract

摘要： 宽度为m的图G的直径是最小整数d，使得G中任何两顶点之间至少存在m条其长度都不超过d的内点不交的路.对于任何满足2w+5[]3≤m≤w的整数m,给出了n阶w正则w连通图的m宽直径的上界为(n-2)(w-2)[](w-m+1)(3m-w-4)+1.它能导出和改进某些已知结果.

关键词: 图论, 连通度, 直径, 宽直径, 正则图, 网络, 容错性

Abstract: The diameter with width m of a graph G is defined as the minimum integer d for which between any two distinct vertices in G there exist at least m internally disjoint paths of length of at most d. It was shown that the tight upper bound on m-diameter of w-regular w-connected graph with order n is(n-2)(w-2)[](w-m+1)(3m-w-4)+1 for any integer m with 2w+5[]3≤m≤w. Some known results can be deduced or improved from the obtained result.

Key words: graphs, connectivity, diameter, wide-diameter, regular graphs, networks, fault tolerance

李佳傲，徐俊明. 正则图的宽直径[J]. 中国科学技术大学学报, 2013, 43(8): 603-606.

LI Jiaao, XU Junming. The wide-diameter of regular graphs[J]. Journal of University of Science and Technology of China, 2013, 43(8): 603-606.

[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]	魏俣童, 鲍秉坤, 张子祺, 朱进. 不稳定传输中受损视频的低延迟修复方法[J]. 中国科学技术大学学报, 2021, 51(10): 717-724.
[6]	刘森, 张直政, 俞涛, 陈志波. 基于网格流的视频修补网络[J]. 中国科学技术大学学报, 2021, 51(1): 1-11.
[7]	朱巧慧, 梁启鹏, 康宇, 赵云波. 无界DoS攻击下网络控制系统的多路径切换保护[J]. 中国科学技术大学学报, 2021, 51(1): 22-32.
[8]	张文静，班志杰. 基于全局的引文网络影响力最大化算法[J]. 中国科学技术大学学报, 2020, 50(8): 1058-1063.
[9]	陶陶，柏建树，刘恒，侯书东，郑啸. 基于WGAN反馈的深度学习差分隐私保护方法[J]. 中国科学技术大学学报, 2020, 50(8): 1064-1071.
[10]	崔文泉，王青芳. 基于双编码器利用在线社交网络信息的股票价格预测[J]. 中国科学技术大学学报, 2020, 50(8): 1093-1101.
[11]	孙磊，张义宁，薛艳芳，乔立山，张丽梅. 自适应功能连接网络学习及其在脑疾病识别中的应用[J]. 中国科学技术大学学报, 2020, 50(8): 1102-1109.
[12]	白江波，杨阳，张文生. 基于改进CycleGAN的合成孔径雷达图像仿真[J]. 中国科学技术大学学报, 2020, 50(8): 1181-1186.
[13]	辛守宇，郑蕊蕊，周瑜，刘文鹏，贺建军. 训练过程中使用支持集信息的单样本学习算法[J]. 中国科学技术大学学报, 2020, 50(8): 1187-1192.
[14]	王悦，李京. 基于可视化的卷积神经网络优化方法研究[J]. 中国科学技术大学学报, 2020, 50(7): 959-967.
[15]	崔文泉，余厚莹，侯晓天. 不均衡数据情形的基于聚焦损失的CGAN的集成分类方法[J]. 中国科学技术大学学报, 2020, 50(7): 968-976.

正则图的宽直径

The wide-diameter of regular graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价