限制弧连通有向图的充分条件

2011-01-09王世英

太原师范学院学报(自然科学版) 2011年3期

关键词：有向图子图情形

伊辉王世英

（山西大学数学科学学院，山西太原 030006）

限制弧连通有向图的充分条件

伊辉王世英

（山西大学数学科学学院，山西太原 030006）

强连通；围长；强分支；限制弧连通度

0 引言

设D＝（V（D），A（D））是没有环和重弧的有限有向图，其中V（D）和A（D）分别是D的顶点集和弧集.D的顶点数n＝|V（D）|称为D的阶.若弧uv∈A（D），则称u控制v，记为u→v，称u和v分别为弧uv的尾和头.顶点v∈V（D）的出度d＋（v）＝（v）是D中v抽控制的顶点数，入度d－（v）＝（v）是D中控制v的顶点数.若D中的一条有向路P＝x1x2…x k满足k≥2为整数且x1＝x k＋1，则称P为一个长为k的有向圈，记为有向k圈.围长g＝g（D）是指D中最短圈的长.

若有向图D的任意两个顶点之间都存在有向路，则称D是强连通的.假设X是V（D）的一个非空子集，以X为顶点集，以两端点均在X中的弧的全体为弧集所组成的有向图H，称为D的由X导出子图，记为D〈X〉，D〈X〉称为D的导出子图.有向图D的极大强连通导出子图称为D的强分支.设D是强连通有向图.任取包含至多k－1条弧的弧子集S，若子图D－S仍是强连通的，则称D是k-弧连通的.称D的一个弧子集S是D的弧割，如果D－S是不强连通的.D的弧连通度λ＝λ（D）是指最小弧割所含的弧数.称D的一个弧子集S是D的限制弧割，如果D－S中存在一个非平凡的强连通分支D1使得D－V（D1）包含至少一条弧.若强连通的有向图D存在限制弧割，则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度，记为λ′（D）［1］.

近年来，有向图的限制弧连通性得到了广泛关注［1，3］，在文［1］中，Volkmann证明：阶至少为4，围长为2或3的强连通有向图D是λ′-连通的且满足λ（D）≤λ′（D）≤ξ（D），除非D是某几类特殊图.本文证明了阶至少为6，围长为4的强连通有向图D是λ′-连通的且满足λ（D）≤λ′（D）≤ξ（D）.

1 主要结论

引理1［1］强连通有向图D是λ′-连通的当且仅当D有一个长为g（D）的有向圈C，满足D－V（C）包含一条弧.

如果D是围长为4的强连通有向图，首先我们定义3种特殊图类.任取正整数p，q，r，t，设顶点集X＝｛x1，x2，…，x p｝，Y＝｛y1，y2…，y q｝，Z＝｛z1，z2，…，zr｝，W＝｛w1，w2，…，w t｝.

H1是一类有向图的集合，任取D∈H1，D的顶点集是｛u，v，w，z｝∪X∪Y∪Z∪W，弧集包含弧uv，vw，wz，zu且u→x i→v（i＝1，2，…，p），v→y j→w（j＝1，2，…，q），w→zm→z（m＝1，2，…，r），z→w l→u（l＝1，2，…，t），其中X，Y，Z，W可以为空集.

H2是一类有向图的集合，任取D∈H2，D的顶点集是｛u，v，w，z，s｝∪X∪Y∪Z，弧集包含弧uv，vw，wz，zu，ws，su且当Y和Z为空集时，x i与u，w相邻并且d＋（x i）＝d－（x i）＝1（i＝1，2，…，p）；当Y或Z为非空时，w→x i→u（i＝1，2，…，p），u→y j→v（j＝1，2，…，q），v→zm→w（m＝1，2，…，r）.

H3是一类有向图的集合，任取D∈H3，D的顶点集是｛u，v，w，z，s｝∪X，弧集包含弧uv，vw，wz，zu，ws，su且s与z相邻，u→x i→w（i＝1，2，…，p）.

定理1 设D是围长为4且阶数n≥6的强连通有向图，如果D不属于图类H1，H2，H3，那么D是λ′-连通的且λ（D）≤λ′（D）≤ξ（D）.

证明显然若D是λ′-连通的，则根据定义可得λ（D）≤λ′（D）成立，所以只需证明D是λ′-连通的且λ′（D）≤ξ（D）即可.设C1＝uvwzu为D的一个有向4圈，且满足d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.若D－V（C1）包含一条弧，则D是λ′-连通的且λ′（D）≤ξ（D）.否则D－V（C1）由弧立点构成.由于D不属于H1且D是强连通有向图，所以存在s∈V（D－V（C1）），u，v∈V（C1），满足w→s→u且d＋（s）≤2，d－（s）≤2，显然C2＝uvwsu为有向4圈.以下分两种情形讨论

情形1d＋（s）＝d－（s）＝1.

若d＋（z）＝d－（z）＝1，则D属于图类H2，与假设矛盾.因此存在一个顶点x∉｛u，v，w，s｝满足x与z相邻，则d＋（z）≥1且d－（z）≥1.设S′是以u，v，w为尾的弧集且令S＝S′＼｛uv，vw，ws｝，那么D－S有一个包含C2的强分支D1，且D－V（D1）包含一条弧zx或xz，因此D是λ′-连通的且

情形2d＋（s）≠1或d－（s）≠1.

若d＋（s）＝1且d－（s）＝2.由于D－V（C1）由弧立点构成且D的围长为4，所以z→s，此时d＋（z）≥2.因此

若d＋（s）＝d－（s）＝2则由D－V（C1）由弧立点构成，此时D中包含有向3圈，矛盾.

若d＋（s）＝2且d－（s）＝1.此时s→z且d＋（z）≥1.以下分两种情形讨论：

情形2.1z仅与u，w，s相邻.

由于n≥6，所以存在顶点集X＝｛x1，x，…，x p｝⊆V（D－C1）＼｛s｝，满足X中每个顶点均与u，w相邻.若u→x i→w（i＝1，2，…，p），则D属于图类H3，矛盾.所以至少存在一个顶点x1，满足w→x1→u，此时d＋（x1）＝1.设S′是以u，v，w为尾的弧集且令S＝S′＼｛uv，vw，w x1｝，那么D－S有一个包含有向4圈uvw x1u的强分支D1，且D－V（D1）包含一条弧sz，因此D是λ′-连通的且

情形2.2 存在x∉｛u，w，s｝，满足z与x相邻.

由于D的围长为4，故x≠v.假设z→x，此时d＋（z）≥2.设S′是以u，v，w为尾的弧集且令S＝S′＼｛uv，vw，ws｝，那么D－S有一个包含C2的强分支D1，且D－V（D1）包含弧zx，因此D是λ′-连通的且

假设x→z.以下分两种情形讨论

情形2.2.1x与u相邻.

若u→x，则uxzu为有向3圈，矛盾.

若x→u，由于D是强连通的，则w→x或v→x.若v→x，则存在有向3圈uvxu，矛盾.所以w→x.当n＝6时，取弧集S1＝｛zu，xu｝，那么D－S1有一个包含C2的强分支D1，且D－V（D1）包含弧zx，因此D是λ′-连通的且λ′（D）≤︳S1︳＝2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.当n≥7时，则存在一个顶点y∈V（D）＼｛u，v，w，z，s，x｝.若z→y，则d＋（z）≥2.此时强连通有向图D是λ′-连通的且

若y→z或y不与z相邻.取弧集S2＝｛zu，xu｝，那么D－S2有一个包含C2的强分支D2.且D－V（D2）包含弧xz，因此D是λ′-连通的且λ′（D）≤︳S2|＝2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.

情形2.2.2x与u不相邻.

若x→v，由于D是强连通的，则w→x，此时D中包含有向3圈xvw x，所以v→x.当n＝6时，设S3是D中删掉除了弧xz外与x关联的弧集，那么D－S3有一个包含C2的强分支D3，且D－V（D3）包含弧xz，因此D是λ′-连通的且λ′（D）≤︳S3︳≤2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.当N≥7时，则存在一个顶点y∈V（D）＼｛u，v，w，z，s，x｝.若z→y，则d＋（z）≥2.此时强连通有向图D是λ′-连通的且

若y→z或y不与z相邻.设S4是D中删掉除了弧xz外与x关联的弧集，那么D－S4有一个包含C2的强分支D4，且D－V（D4）包含弧xz，因此D是λ′-连通的且

λ′（D）≤ ︳S4︳ ≤2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.

定理2 设D是围长g（D）≥4且阶数n≥g（D）＋2的强连通有向图，若对任意的x∈V（D），满足d＋（x）≥2且d－（x）≥2，则D是λ′-连通的.

证明用反证法，假设D不是λ′-连通的.由引理1，任取D中长为g（D）的一个向圈C，D－V（C）是由孤立点组成.由于d＋（x）≥2且d－（x）≥2，所以若x∉V（C），则x在D中被C上至少2个顶点所控制且控制C上至少2个顶点.若x∈V（C），则x与C上任意一个不相邻顶点之间在D中不可能有弧，否则D中存在长小于g（D）的有向圈，那么任意的x∈V（C）在D中被D－V（C）中至少1个顶点所控制且控制D－V（C）中至少1个顶点.令C＝u1u2…u gu1，设u1控制D－V（C）中的1个顶点y，由于d＋（y）≥2，所以y只能控制u2，u3，否则D中将存在长小于g（D）的有向圈，矛盾.又d－（y）≥2，则存在ui∈V（C）＼｛u1｝满足ui→y，此时D中必出现长小于g（D）的有向圈，矛盾.

［1］Lutz Volkmann.Restricted arc-connectivity 0f digraphs［J］.Information Processing Letters，2007，103（6）：234-239

［2］Jorgen Bang-Jensen，Gregory Gutin.Digraphs：Theory，Algorithms and Applications［M］.London：Springer-Verlag，2007

［3］Wang Shiying，Lin Shangwci.V-optimal digraphs［J］.Information Processing Letters，2008，108（6）：386-389

［4］王世英，林上为.网络边连通性的最优化［M］.北京：科学出版社，2009

Sufficient Conditions for Restricted Arc-Connected Digraphs

Yi Hui Wang Shiying
（School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China）