非極大弧連通有向圖弧連通度的下界

王曉麗，王世英

（1．晉中學院數學學院，山西 榆次 030600；2．山西大學數學科學學院，山西 太原 030006）

非極大弧連通有向圖弧連通度的下界

王曉麗1，王世英2

（1．晉中學院數學學院，山西 榆次 030600；2．山西大學數學科學學院，山西 太原 030006）

設D是一個有向圖，δ（D）是最小度，弧連通度為λ（D），則λ（D）≤δ（D）。當λ（D）＜δ（D）時，稱有向圖D是非極大弧連通的。本文給出了非極大弧連通圖的弧連通度的下界。

有向圖；弧連通度；度序列；團數

1 引言

如果D的任意兩個不同的頂點u，v，在D中都存在（u，v）－路，則稱D為強連通的。對于強連通有向圖D，若存在一個弧集SA（D），使得D-S不是強連通的，則稱S是D的一個弧割?；底钌俚幕「罘Q為最小弧割。D的弧連通度λ（D）定義為D的最小弧割中弧的數目。由定義顯然λ（D）≤δ（D）。當λ（D）＜δ（D）時，稱有向圖D是非極大弧連通的。設D是一個有向圖，令D1，D2，…，Dt是D的所有強連通分支排成的一個序列，若對任意的uv∈A（D），其中u∈A（Di），v∈A（Dj）都滿足i＜j，則稱上述的序列是D的一個強連通分支無圈序。

對整數p≥2，去掉有向圖D中弧的方向，再去掉產生的重邊得到的簡單圖若不含p＋1階的完全子圖，稱D的團數ω（D）≤p。若X是V（D）的非空真子集，記＝V＼X。對有二分類V′，V″的二部有向圖D及ZV（D），令Z′＝Z∩V′，Z″＝Z∩V″，本文未給出的術語和記號請參見文［1］。

文獻［2］討論了有向圖點連通度的下界，本文討論非極大弧連通圖的弧連通度的下界。

2 主要結論

引理1［3］設（X，Y）為有向圖D的任一滿足｜（X，Y）｜≤δ－1的弧割，則｜X｜≥δ＋＋1，｜Y｜≥δ－＋1，且｜X｜≥ξ＋＋2，｜Y｜≥ξ－＋2。

證明設S是D的最小弧割，則｜S｜＝λ且D-S至少包含兩個強連通分支。設D1，D2，…，Dk（k≥2）是D-S的強連通分支無圈序。令X＝V（Dk），Y＝V（D）＼V（Dk），由強連通分支無圈序的定義知，D-S中（X，Y）＝?。注意到D是強連通的，所以在D中（X，Y）≠?。從而（X，Y）S。又因為（X，Y）是D的一個弧割且S是最小弧割，故（X，Y）＝S。因為λ＜δ，所以由引理1知｜X｜≥δ＋＋1，｜Y｜≥δ－＋1，同時｜X｜≥ξ＋＋2，｜Y｜≥ξ－＋2，即｜X｜，｜Y｜≥max｛δ＋1，ξ＋2｝＝t。

將X中的點按度的不增序排列，由前t個頂點組成的集合記為U。將Y中的點按度的不增序排列，由前t個頂點組成的集合記為W。則我們有

故

證明設S是D的最小弧割，則｜S｜＝λ且D-S至少包含兩個強連通分支。設D1，D2，…，Dk（k≥2）是D-S的強連通分支無圈序。令X＝V（D1），Y＝V（Dk），由強連通分支無圈序的定義知，D-S中（Y，ˉY）＝?，，X）＝?，且｜X｜，｜Y｜≥2。若｜X｜＝1，設X＝｛x｝，則δ≤δ－≤d－（x）≤｜S｜＝λ，與λ＜δ矛盾，故｜X｜≥2。同理可證｜Y｜≥2。由于｜X｜，｜Y｜≥2，且D1，Dk是強連通的，故這兩個分支D1，Dk都至少包含兩條弧，設u1v1∈A（D1），u2v2∈A（Dk）。則我們有

故結論成立。

矛盾，故結論成立。

則我們有

引理6［3］設（X，Y）是二部有向圖D的任一滿足｜（X，Y）｜≤δ－1的弧割，則｜X′｜，｜X″｜≥δ＋，｜Y′｜，｜Y″｜≥δ－。

證明設S是D的最小弧割，則｜S｜＝λ且D-S至少包含兩個強連通分支。設D1，D2，…，Dk（k≥2）是D-S的強連通分支無圈序。令X＝V（Dk），Y＝V（D）＼V（Dk），則（X，Y）＝S。因為λ＜δ，所以由引理6，知｜X′｜，｜X″｜≥δ＋，｜Y′｜，｜Y″｜≥δ－。即｜X′｜，｜X″｜≥δ，｜Y′｜，｜Y″｜≥δ。

將X′中的點按度的不增序排列，由前δ個頂點組成的集合記為U′。將X″中的點按度的不增序排列，由前δ個頂點組成的集合記為U″。將Y′中的點按度的不增序排列，由前δ個頂點組成的集合記為W′。將Y″中的點按度的不增序排列，由前δ個頂點組成的集合記為W″。則我們有

由此可得

［1］BANG-JENSENJ，GREGORYG．Digraphs：theory，algorithmsandapplications［M］．London：Springer-Verlag，2001．

［2］HELLWIGA，VOLKMANNL．Lowerboundsonthevertex-connectivityofdigraphsandgraphs［J］．InformationProcessing Letters，2006，99（2）：41－46．

［3］高敬振．有向圖的邊割（X，Y）中｜X｜和｜Y｜的下界與有向圖的極大性和超級性［J］．系統科學與數學，2011，12（5）：1603－1611．

［4］TURáNP．Anextremalproblemingraphtheory［J］．MatematikaiésFizikaiLapok，1941，48：436－452．

Lower bounds of the arc-connectivity of a non-maximally arc-connected digraph

WANG Xiao-Ii1，WANG Shi-ying2
（1．School of Mathematics，Jinzhong University，Jinzhong 030600，China；2．School of Mathematics，Shanxi University，Taiyuan 030006，China）

Let D be a digraph and δ（D）be its minimum degree．Then λ（D）≤δ（D）exists．A digraph D is non-maximally arc-connected if λ（D）＜δ（D）．This paper presents the lower bounds of the arc-connectivity of a non-maximally arcconnected digraph．

digraph；arc-connectivity；degree sequence；clique number

O157.5

A

1002-4026（2014）01-0098-04

10.3976／j.issn.1002－4026.2014.01.017

2013-04-01

國家自然科學基金（61070229）；國家教育部博士點基金（博導類）（20111401110005）

王曉麗（1982－），女，碩士，研究方向為圖論。