扩张竞赛图中的泛连通性点对

• 作者: 刘爱霞 原军
• 来源期刊: 太原科技大学学报
• 学科: 数学
• 关键词: Hamilton路 扩张竞赛图 泛连通性点对
• 年，卷（期）: 2013,（4）
• 所属期刊栏目: 应用科学
• 页码范围: 317-320
• 页数: 4页
• 分类号: O157.5
• 字数: 3742字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-2057.2013.04.016

摘要

研究了扩张竞赛图中的泛连通性点对的存在性问题.证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对.研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,Dt是连通但非强连通的扩张竞赛图D的一个强分支无圈序.若Di(i=1,2,…,t)有1-路-圈因子,则D中必存在泛连通性点对.并且找到泛连通性点对的时间复杂度为D(n2.5).(b)设D是由连通但非强连通竞赛图T的强分支Ti(| V(Ti)|≥3)平衡扩张而成的,(当| V(Ti)|=1时,Ti不变),则D中必存在泛连通性点对.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原军	太原科技大学应用科学学院	19	3	1.0	1.0
2	刘爱霞	太原科技大学应用科学学院	6	1	1.0	1.0