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

The k-restricted Arc Connectivity of Cartesian Product Digraphs

作　　者：晋亚男 林上为[1] JIN Ya’nan;LIN Shangwei(School of Mathematical Sciences,Shanxi University,Taiyuan 030006,Shanxi China)

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《河南科学》2017年第3期345-349,共5页Henan Science

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

摘　　要：笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.The cartesian product digraph is one of the most important models for large-scale interconnectednetworks.As a common generalization of the arc connectivity and the restricted arc connectivity,the k-restrictedarc connectivity of digraphs can be used to measure the reliability of networks.Let D be a strong digraph.An arcsubset S is a k-restricted arc that cut of D if D-S has a strong component D1with order at least k such as D-V(D1)contains a connected subdigraph with order at least k.If the k-restricted arc cut exists,then D is calledλk-connected.The k-restricted arc connectivityλ(k D1)of aλk-connected digraph D is the minimum cardinality overall k-restricted arc cuts.In this paper,we show an upper bound on the k-restricted arc connectivity of cartesianproduct digraphs and a lower bound on the3-restricted arc connectivity of cartesian product digraphs,which extendsthe results of2-restricted arc connectivity.Furthermore,we give an example to show that these bounds are sharp.

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

分 类 号：O157.5[理学—数学]