有向线图的限制性连通度

• 作者: 张昭 祝玉芳
• 来源期刊: 数学研究
• 学科: 数学
• 关键词: 有向线图 限制性连通度
• 年，卷（期）: 2010,（2）
• 页码范围: 107-113
• 分类号: O151
• 字数: 2310字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-6837.2010.02.001

摘要

设D=(V(D),A(D))是一个强连通有向图.弧集S A(D)称为D的κ-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于κ.最小κ-限制性弧割的基数称为κ-限制性弧连通度,记作λκ(D).κ-限制性点连通度Kκ(D)可以类似地定义.有κ-限制性弧割(κ-限制性点割)的有向图称为λk-连通(Kκ-连通)有向图.本文研究有向图D的限制性弧连通度和其线图L(D)的限制性点连通度的关系,证明了对任意λκ-连通有向图D,Kκ(LD))≤λκ(D),当κ=2,3时等式成立;若L(D)是Kκ(κ-1)-连通的,则λκ(D)≤κκ(κ-1)(L(D));特别地,若D是一个定向图且L(D)是Kκ(k-1)/2-连通的,贝λκ(D)S ≤Kκ(κ-1)/2(L(D)).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张昭	新疆大学数学与系统科学学院	16	23	3.0	4.0
2	祝玉芳	新疆大学数学与系统科学学院	1	1	1.0	1.0