限制弧連通有向圖的充分條件

伊 輝 王世英

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

限制弧連通有向圖的充分條件

伊 輝 王世英

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

強(qiáng)連通；圍長(zhǎng)；強(qiáng)分支；限制弧連通度

0 引言

設(shè)D＝（V（D），A（D））是沒(méi)有環(huán)和重弧的有限有向圖，其中V（D）和A（D）分別是D的頂點(diǎn)集和弧集.D的頂點(diǎn)數(shù)n＝|V（D）|稱為D的階.若弧uv∈A（D），則稱u控制v，記為u→v，稱u和v分別為弧uv的尾和頭.頂點(diǎn)v∈V（D）的出度d＋（v）＝（v）是D中v抽控制的頂點(diǎn)數(shù)，入度d－（v）＝（v）是D中控制v的頂點(diǎn)數(shù).若D中的一條有向路P＝x1x2…x k滿足k≥2為整數(shù)且x1＝x k＋1，則稱P為一個(gè)長(zhǎng)為k的有向圈，記為有向k圈.圍長(zhǎng)g＝g（D）是指D中最短圈的長(zhǎng).

若有向圖D的任意兩個(gè)頂點(diǎn)之間都存在有向路，則稱D是強(qiáng)連通的.假設(shè)X是V（D）的一個(gè)非空子集，以X為頂點(diǎn)集，以兩端點(diǎn)均在X中的弧的全體為弧集所組成的有向圖H，稱為D的由X導(dǎo)出子圖，記為D〈X〉，D〈X〉稱為D的導(dǎo)出子圖.有向圖D的極大強(qiáng)連通導(dǎo)出子圖稱為D的強(qiáng)分支.設(shè)D是強(qiáng)連通有向圖.任取包含至多k－1條弧的弧子集S，若子圖D－S仍是強(qiáng)連通的，則稱D是k-弧連通的.稱D的一個(gè)弧子集S是D的弧割，如果D－S是不強(qiáng)連通的.D的弧連通度λ＝λ（D）是指最小弧割所含的弧數(shù).稱D的一個(gè)弧子集S是D的限制弧割，如果D－S中存在一個(gè)非平凡的強(qiáng)連通分支D1使得D－V（D1）包含至少一條弧.若強(qiáng)連通的有向圖D存在限制弧割，則稱D是λ′-連通的.λ′-連通圖D的最小限制弧割所含的弧數(shù)稱為D的限制弧連通度，記為λ′（D）［1］.

近年來(lái)，有向圖的限制弧連通性得到了廣泛關(guān)注［1，3］，在文［1］中，Volkmann證明：階至少為4，圍長(zhǎng)為2或3的強(qiáng)連通有向圖D是λ′-連通的且滿足λ（D）≤λ′（D）≤ξ（D），除非D是某幾類特殊圖.本文證明了階至少為6，圍長(zhǎng)為4的強(qiáng)連通有向圖D是λ′-連通的且滿足λ（D）≤λ′（D）≤ξ（D）.

1 主要結(jié)論

引理1［1］強(qiáng)連通有向圖D是λ′-連通的當(dāng)且僅當(dāng)D有一個(gè)長(zhǎng)為g（D）的有向圈C，滿足D－V（C）包含一條弧.

如果D是圍長(zhǎng)為4的強(qiáng)連通有向圖，首先我們定義3種特殊圖類.任取正整數(shù)p，q，r，t，設(shè)頂點(diǎn)集X＝｛x1，x2，…，x p｝，Y＝｛y1，y2…，y q｝，Z＝｛z1，z2，…，zr｝，W＝｛w1，w2，…，w t｝.

H1是一類有向圖的集合，任取D∈H1，D的頂點(diǎn)集是｛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的頂點(diǎn)集是｛u，v，w，z，s｝∪X∪Y∪Z，弧集包含弧uv，vw，wz，zu，ws，su且當(dāng)Y和Z為空集時(shí)，x i與u，w相鄰并且d＋（x i）＝d－（x i）＝1（i＝1，2，…，p）；當(dāng)Y或Z為非空時(shí)，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的頂點(diǎn)集是｛u，v，w，z，s｝∪X，弧集包含弧uv，vw，wz，zu，ws，su且s與z相鄰，u→x i→w（i＝1，2，…，p）.

定理1 設(shè)D是圍長(zhǎng)為4且階數(shù)n≥6的強(qiáng)連通有向圖，如果D不屬于圖類H1，H2，H3，那么D是λ′-連通的且λ（D）≤λ′（D）≤ξ（D）.

證明 顯然若D是λ′-連通的，則根據(jù)定義可得λ（D）≤λ′（D）成立，所以只需證明D是λ′-連通的且λ′（D）≤ξ（D）即可.設(shè)C1＝uvwzu為D的一個(gè)有向4圈，且滿足d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.若D－V（C1）包含一條弧，則D是λ′-連通的且λ′（D）≤ξ（D）.否則D－V（C1）由弧立點(diǎn)構(gòu)成.由于D不屬于H1且D是強(qiáng)連通有向圖，所以存在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，與假設(shè)矛盾.因此存在一個(gè)頂點(diǎn)x?｛u，v，w，s｝滿足x與z相鄰，則d＋（z）≥1且d－（z）≥1.設(shè)S′是以u(píng)，v，w為尾的弧集且令S＝S′＼｛uv，vw，ws｝，那么D－S有一個(gè)包含C2的強(qiáng)分支D1，且D－V（D1）包含一條弧zx或xz，因此D是λ′-連通的且

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

若d＋（s）＝1且d－（s）＝2.由于D－V（C1）由弧立點(diǎn)構(gòu)成且D的圍長(zhǎng)為4，所以z→s，此時(shí)d＋（z）≥2.因此

若d＋（s）＝d－（s）＝2則由D－V（C1）由弧立點(diǎn)構(gòu)成，此時(shí)D中包含有向3圈，矛盾.

若d＋（s）＝2且d－（s）＝1.此時(shí)s→z且d＋（z）≥1.以下分兩種情形討論：

情形2.1z僅與u，w，s相鄰.

由于n≥6，所以存在頂點(diǎn)集X＝｛x1，x，…，x p｝?V（D－C1）＼｛s｝，滿足X中每個(gè)頂點(diǎn)均與u，w相鄰.若u→x i→w（i＝1，2，…，p），則D屬于圖類H3，矛盾.所以至少存在一個(gè)頂點(diǎn)x1，滿足w→x1→u，此時(shí)d＋（x1）＝1.設(shè)S′是以u(píng)，v，w為尾的弧集且令S＝S′＼｛uv，vw，w x1｝，那么D－S有一個(gè)包含有向4圈uvw x1u的強(qiáng)分支D1，且D－V（D1）包含一條弧sz，因此D是λ′-連通的且

情形2.2 存在x?｛u，w，s｝，滿足z與x相鄰.

由于D的圍長(zhǎng)為4，故x≠v.假設(shè)z→x，此時(shí)d＋（z）≥2.設(shè)S′是以u(píng)，v，w為尾的弧集且令S＝S′＼｛uv，vw，ws｝，那么D－S有一個(gè)包含C2的強(qiáng)分支D1，且D－V（D1）包含弧zx，因此D是λ′-連通的且

假設(shè)x→z.以下分兩種情形討論

情形2.2.1x與u相鄰.

若u→x，則uxzu為有向3圈，矛盾.

若x→u，由于D是強(qiáng)連通的，則w→x或v→x.若v→x，則存在有向3圈uvxu，矛盾.所以w→x.當(dāng)n＝6時(shí)，取弧集S1＝｛zu，xu｝，那么D－S1有一個(gè)包含C2的強(qiáng)分支D1，且D－V（D1）包含弧zx，因此D是λ′-連通的且λ′（D）≤︳S1︳＝2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.當(dāng)n≥7時(shí)，則存在一個(gè)頂點(diǎn)y∈V（D）＼｛u，v，w，z，s，x｝.若z→y，則d＋（z）≥2.此時(shí)強(qiáng)連通有向圖D是λ′-連通的且

若y→z或y不與z相鄰.取弧集S2＝｛zu，xu｝，那么D－S2有一個(gè)包含C2的強(qiáng)分支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是強(qiáng)連通的，則w→x，此時(shí)D中包含有向3圈xvw x，所以v→x.當(dāng)n＝6時(shí)，設(shè)S3是D中刪掉除了弧xz外與x關(guān)聯(lián)的弧集，那么D－S3有一個(gè)包含C2的強(qiáng)分支D3，且D－V（D3）包含弧xz，因此D是λ′-連通的且λ′（D）≤︳S3︳≤2≤d＋（u）＋d＋（v）＋d＋（w）＋d＋（z）－4＝ξ（D）.當(dāng)N≥7時(shí)，則存在一個(gè)頂點(diǎn)y∈V（D）＼｛u，v，w，z，s，x｝.若z→y，則d＋（z）≥2.此時(shí)強(qiáng)連通有向圖D是λ′-連通的且

若y→z或y不與z相鄰.設(shè)S4是D中刪掉除了弧xz外與x關(guān)聯(lián)的弧集，那么D－S4有一個(gè)包含C2的強(qiáng)分支D4，且D－V（D4）包含弧xz，因此D是λ′-連通的且

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

定理2 設(shè)D是圍長(zhǎng)g（D）≥4且階數(shù)n≥g（D）＋2的強(qiáng)連通有向圖，若對(duì)任意的x∈V（D），滿足d＋（x）≥2且d－（x）≥2，則D是λ′-連通的.

證明用反證法，假設(shè)D不是λ′-連通的.由引理1，任取D中長(zhǎng)為g（D）的一個(gè)向圈C，D－V（C）是由孤立點(diǎn)組成.由于d＋（x）≥2且d－（x）≥2，所以若x?V（C），則x在D中被C上至少2個(gè)頂點(diǎn)所控制且控制C上至少2個(gè)頂點(diǎn).若x∈V（C），則x與C上任意一個(gè)不相鄰頂點(diǎn)之間在D中不可能有弧，否則D中存在長(zhǎng)小于g（D）的有向圈，那么任意的x∈V（C）在D中被D－V（C）中至少1個(gè)頂點(diǎn)所控制且控制D－V（C）中至少1個(gè)頂點(diǎn).令C＝u1u2…u gu1，設(shè)u1控制D－V（C）中的1個(gè)頂點(diǎn)y，由于d＋（y）≥2，所以y只能控制u2，u3，否則D中將存在長(zhǎng)小于g（D）的有向圈，矛盾.又d－（y）≥2，則存在ui∈V（C）＼｛u1｝滿足ui→y，此時(shí)D中必出現(xiàn)長(zhǎng)小于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］王世英，林上為.網(wǎng)絡(luò)邊連通性的最優(yōu)化［M］.北京：科學(xué)出版社，2009

Sufficient Conditions for Restricted Arc-Connected Digraphs

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

strongly connected；girths；strong component；restricted arc-connectivity

1672-2027（2011）03-0013-04

O157.5

A

2011-4-15

國(guó)家自然科學(xué)基金（61070229）.

伊 輝（1987-），男，山西臨沂人，山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院在讀碩士研究生，主要從事圖論及其應(yīng)用研究.