有向笛卡尔积图的k-限制弧连通度

摘要：

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D1,使得D-V(D1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λk-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λk(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.

关键词：网络、有向图、笛卡尔积、弧连通度

所属期刊栏目：35

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金61202017;中国博士后基金2012M510579

在线出版日期：2017-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：345-349