λ5－最優(yōu)圖的鄰域交條件

張國珍，王世英

（山西大學數學科學學院，山西太原030006）

λ5－最優(yōu)圖的鄰域交條件

張國珍，王世英

（山西大學數學科學學院，山西太原030006）

給出了λ5－最優(yōu)圖的鄰域交條件：設G是一個階至少為10的連通圖，對G中任意一對不相鄰頂點u和v，若u，v均不在三角形中，有｜N（u）∩N（v）｜≥6，若u或v在三角形中，有｜N（u）∩N（v）｜≥9，則G是λ5－最優(yōu)的；若G中任意一對不相鄰頂點u和v滿足｜N（u）∩N（v）｜≥7，任意一條邊xy滿足｜N（x）∩N（y）｜≤3，則G是λ5－最優(yōu)的．

限制邊割；限制邊連通度；鄰域

0 引言

用G＝（V，E）表示點集為V＝V（G），邊集E＝E（G）的有限簡單無向圖．稱圖G的頂點數｜V（G）｜為圖G的階．對G的任意一點u，稱G中所有與u相鄰的點所成的集合N（u）為u的鄰域，稱N（u）中頂點數目為u的度，記為d（u）．對G的兩個非空頂點子集A，B，用［A，B］表示G中一端點在A中另一端點在B中的所有邊所成的集合，用珡A表示A的補集V＼A．對于文中其它未加定義而被使用的圖論術語和記號請參見文［1］．

多處理機的互連網絡拓撲通常以圖為數學模型，這時圖的頂點代表處理機，而一對處理機之間的直接通信聯(lián)系則用連接這對頂點的邊來表示，因此網絡拓撲的性能可以通過圖的性質和參數來度量［2－6］．在設計和選擇互聯(lián)網絡拓撲結構時，要考慮的一個問題是系統(tǒng)的可靠性能．邊連通度是度量網絡可靠性的一個重要參數．不過，這個參數也有一些缺陷，比如：它不能準確反映由于信關的損壞而造成的系統(tǒng)損壞程度，也不能處理某些部分不會同時損壞的網絡的可靠性［2］．在此背景下，k－限制邊連通度的概念被提出．

設G是一個連通圖，S是G的一個邊割，如果G－S的每個分支至少有k個頂點，則稱S是G的一個k－限制邊割．定義λk＝λk（G）＝min｛｜S｜∶S為G的k－限制邊割｝為G的k－限制邊連通度，達到最小的這種S稱為G的λk－割．如果G存在k－限制邊割，則稱G是λk－連通的．設H是G的一個子圖，令?（H）表示恰好有一個端點在H上的邊的數目．定義ξk＝ξk（G）＝min｛?（H）∶H是G的k階連通子圖｝．如果λk（G）＝ξk（G），則稱G是λk－最優(yōu)的．在λk－最優(yōu)圖的鄰域交條件方面，已有：

定理1［3］設G是階至少為4的一個連通圖，對G中任意一對不相鄰頂點u，v，若u，v均不在三角形上，有｜N（u）∩N（v）｜≥2，若u或v在三角形上，有｜N（u）∩N（v）｜≥3，則G是λ2－最優(yōu)的．

定理2［4］設G是一個λ3－連通圖，對G中任意一對不相鄰頂點u，v，若u，v均不在三角形上，有｜N（u）∩N（v）｜≥4，若u或v在三角形上，有｜N（u）∩N（v）｜≥5，則G是λ3－最優(yōu)的．

1 主要結果和證明

引理1 設G是一個階至少為10的連通圖．如果對于G中任意一對不相鄰頂點u和v都有｜N（u）∩N（v）｜≥6，則G是λ5－連通的而且滿足λ5（G）≤ξ5（G）．

證明 因為G是一個頂點數至少為10的連通圖，所以ξ5（G）存在．設H是G的一個5階連通子圖，滿足?（H）＝ξ5（G）．記V（H）＝U．如果G［珡U］中所有點都相鄰，那么G［珡U］顯然是連通的．如果G［珡U］中存在不相鄰的兩點u和v，那么｜N（u）∩N（v）｜≥6．由于｜N（u）∩N（v）∩U｜≤5，則｜N（u）∩N（v）∩珡U｜≥6－5＝1．這說明G［珡U］是連通的．由定義［U，珡U］是G的一個5－限制邊割．因此G是λ5－連通的，而且λ5（G）≤｜［U，珡U］｜＝?（H）＝ξ5（G）．

設G為一個連通圖，S為G的一個λk－割，則G－S只有兩個分支G1，G2．記V（G1）＝X，V（G2）＝Y，那么S＝［X，Y］．

引理2［5］設G為滿足λk（G）≤ξk（G）的λk－連通圖，S＝［X，Y］為G的λk－割．如果G1中存在k階連通子圖H，滿足｜［V（H），X＼V（H）］｜≤｜［X＼V（H），Y］｜，則G是λk－最優(yōu)的．

以下考慮k＝5的情況．

推論1 設G為滿足λ5（G）≤ξ5（G）的λ5－連通圖，S＝［X，Y］為G的λ5－割．如果G1中存在5階連通子圖H，滿足對任意的x∈X＼V（H），有｜N（x）∩V（H）｜≤｜N（x）∩Y｜，則G是λ5－最優(yōu)的．特別地，若對任意的x∈X＼V（H），有｜N（x）∩Y｜≥5，則G是λ5－最優(yōu)的．

引理3 設x1，x2，x3是G2中的3個點，H是G2的包含｛x1，x2，x3｝中盡可能多的點且邊數盡可能大的5階連通子圖．若存在x′∈｛x1，x2，x3｝＼V（H），則｜N（x′）∩V（H）｜≤3．

證明 用反證法．假設存在x′∈｛x1，x2，x3｝＼V（H），滿足｜N（x′）∩V（H）｜≥4．不妨設x′＝x1．若H有一棵生成樹T使其存在一個1度頂點y｛x2，x3｝，則在H中去掉y而加上x1所導出的5階子圖連通，且比H多包含了x1，與H的取法矛盾！若H中任意一棵生成樹T的所有1度頂點都是｛x2，x3｝中的點，則H必是一條以x2，x3為端點的路．那么在H中去掉x2而加上x1所導出的5階子圖H′連通，且H′與H有相同的｛x1，x2，x3｝中的點數，但H′的邊數大于H的邊數．與H的取法矛盾！假設錯誤，引理得證．

下面給出并證明本文的主要結論，首先給出一些與證明相關的記號．

設G是λ5－連通圖，對于G的一個λ5－割S＝［X，Y］，把X5X，Y5Y定義為X，Y的與S中至少5條邊相關聯(lián)的點集．XiX，YiY定義為X，Y的與S中恰好i條邊相關聯(lián)的點集（i＝0，1，2，3，4）．

定理3 設G是一個階至少為10的連通圖，對G中任意一對不相鄰頂點u和v，若u，v均不在三角形中，有｜N（u）∩N（v）｜≥6，若u或v在三角形中，有｜N（u）∩N（v）｜≥9，則G是λ5－最優(yōu)的．

證明 由引理1，G是λ5－連通的且滿足λ5（G）≤ξ5（G）．設S是G的一個λ5－割，G－S的兩個分支記為G1，G2，并記X＝V（G1），Y＝V（G2）．可得｜X｜≥5，｜Y｜≥5．若｜X｜＝5或｜Y｜＝5，顯然G是λ5－最優(yōu)的．下設｜X｜≥6，｜Y｜≥6．由推論1可設X≠X5，Y≠Y5．

情形1 存在i≤1滿足Xi≠?或Yi≠?．

不妨設Xi≠?．取x∈Xi，由G2的連通性可知，G2中必存在包含N（x）∩Y的5階連通子圖H．對任意的y∈Y＼V（H），x與y不相鄰，則｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥6－i≥5，由推論1可得G是λ5－最優(yōu)的．

情形2 Xi＝Yi＝?（i＝0，1）；X2＝?或Y2＝?．

不妨設X2≠?，取x∈X2，記N（x）∩Y＝｛x1，x2｝．取G2中包含｛x1，x2｝中盡可能多的點的5階連通子圖H．不妨設H含x1．對任意的y∈Y＼（V（H）∪｛x2｝），x與y不相鄰，則｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥6－2＝4．設存在y∈Y＼（V（H）∪｛x2｝），使得｜N（y）∩X｜＜｜N（y）∩V（H）｜，則｜N（y）∩X｜＝4，｜N（y）∩V（H）｜＝5．由H的連通性可知y必在某個三角形中，由定理條件知4＝｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥9－2＝7，矛盾！故對任意的y∈Y＼（V（H）∪｛x2｝），有｜N（y）∩X｜≥｜N（y）∩V（H）｜．若x2∈V（H），則由推論1可得G是λ5－最優(yōu)的．下設x2V（H）．若｜N（x2）∩V（H）｜≥2，記N（x2）∩V（H）＝｛y1，y2｝．不妨設H中的最短（x1，y1）路P不含y2，則｜V（P）｜≤4．故G2中最短（x1，x2）路上的點數小于等于5．從而G2中存在5階連通子圖包含x1和x2，與H的取法矛盾！故｜N（x2）∩V（H）｜≤1，由Y0＝Y1＝?，｜N（x2）∩X｜≥2．由推論1可得G是λ5－最優(yōu)的．

情形3 Xi＝Yi＝?（i＝0，1，2）；X3≠?或Y3≠?．

不妨設X3≠?，取x∈X3，記N（x）∩Y＝｛x1，x2，x3｝．取G2中的5階連通子圖H，使H包含｛x1，x2，x3｝中盡可能多的點且邊數盡可能大．對任意的x′∈｛x1，x2，x3｝＼V（H），由引理3，｜N（x′）∩V（H）｜≤3．而由Y0＝Y1＝Y2＝?，｜N（x′）∩X｜≥3．下證對任意的y∈Y＼（V（H）∪｛x1，x2，x3｝），有｜N（y）∩X｜≥｜N（y）∩V（H）｜．設存在y∈Y＼（V（H）∪｛x1，x2，x3｝），使得｜N（y）∩X｜＜｜N（y）∩V（H）｜．由｜N（y）∩X｜≥3，則｜N（y）∩V（H）｜≥4．若｜N（y）∩V（H）｜＝5，則由H的連通性知y必在某個三角形中，由定理條件知｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥9－3＝6，與｜N（y）∩X｜＜｜N（y）∩V（H）｜＝5矛盾！若｜N（y）∩V（H）｜＝4．當y在某個三角形中時，同理可得矛盾！下設y不在三角形中，則H=K1，4，且y不與H的4度頂點相鄰．記V（H）＝｛x′1，x′2，x′3，y1，y2｝滿足y1，y2｛x1，x2，x3｝．取H′＝G［｛x′1，x′2，x′3，y，yi｝］，i＝1或2，使得H′包含H的4度頂點．則H′是5階連通子圖，且H′與H有相同的｛x1，x2，x3｝中的點，但H′的邊數大于H的邊數．與H的取法矛盾！由推論1可得G是λ5－最優(yōu)的．

情形4 Xi＝Yi＝?，i＝0，1，2，3．

由X≠X5，故存在x∈X4，記N（X）∩Y＝｛x1，x2，x3，x4｝．取G2中包含｛x1，x2，x3，x4｝中盡可能多的點的5階連通子圖H．不妨設H含x1．對任意的y∈Y＼（V（H）∪｛x2，x3，x4｝），由Y0＝Y1＝Y2＝Y3＝?，｜N（y）∩X｜≥4．設存在y∈Y＼（V（H）∪｛x2，x3，x4｝），使得｜N（y）∩X｜＜｜N（y）∩V（H）｜，則｜N（y）∩X｜＝4，｜N（y）∩V（H）｜＝5．由H的連通性知y必在某個三角形中，由定理條件知4＝｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥9－4＝5．矛盾！故對任意的y∈Y＼（V（H）∪｛x2，x3，x4｝），有｜N（y）∩X｜≥｜N（y）∩V（H）｜．下證若存在x′∈｛x2，x3，x4｝＼V（H），則｜N（x′）∩X｜≥｜N（x′）∩V（H）｜．不妨設x2V（H），由Y0＝Y1＝Y2＝Y3＝?，｜N（x2）∩X｜≥4．假設｜N（x2）∩V（H）｜＝5，則在H中去掉一個非｛x1，x3，x4｝中的點而加上x2所導出的5階子圖連通，且比H多包含了x2，與H的取法矛盾！由推論1可得G是λ5－最優(yōu)的．定理得證．

定理4 設G是一個階至少為10的連通圖，若G中任意一對不相鄰頂點u和v滿足｜N（u）∩N（v）｜≥7，任意一條邊xy滿足｜N（x）∩N（y）｜≤3，則G是λ5－最優(yōu)的．

證明 由引理1，G是λ5－連通的且滿足λ5（G）≤ξ5（G）．設S是G的一個λ5－割，G－S的兩個分支記為G1，G2，并記X＝V（G1），Y＝V（G2）．可得｜X｜≥5，｜Y｜≥5．若｜X｜＝5或｜Y｜＝5，顯然G是λ5－最優(yōu)的．下設｜X｜≥6，｜Y｜≥6．

情形1 存在i≤1滿足Xi≠?或Yi≠?．

不妨設Xi≠?．取x∈Xi，由G2的連通性可知，G2中必存在包含N（x）∩Y的5階連通子圖H．對任意的y∈Y＼V（H），x與y不相鄰，則｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥7－i≥6．由推論1可得G是λ5－最優(yōu)的．

情形2 Xi＝Yi＝?（i＝0，1）；X2≠?或Y2≠?．

不妨設X2≠?，取x∈X2，記N（x）∩Y＝｛x1，x2｝．假設G2中存在包含N（x）∩Y的5階連通子圖H，對任意的y∈Y＼V（H），x與y不相鄰．則｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥7－2＝5．由推論1可得G是λ5－最優(yōu)的．以下假設G2中不存在包含N（x）∩Y的5階連通子圖，記G2中一條最短（x1，x2）路為y1y2…yl，其中y1＝x1，yl＝x2，則l≥6，否則與G2中不存在包含N（x）∩Y的5階連通子圖矛盾！令H＝G［｛y1，y2，y3，y4，y5｝］，則x2在H中至多有一個鄰點，而由Y0＝Y1＝?，可得｜N（x2）∩X｜≥2，故｜N（x2）∩X｜≥｜N（x2）∩V（H）｜．對任意w∈Y＼（V（H）∪｛x2｝），x與w不相鄰，易知｜N（w）∩X｜≥5．由推論1可得G是λ5－最優(yōu)的．

情形3 Xi＝Yi＝?（i＝0，1，2）；X3≠?或Y3≠?．

不妨設X3≠?，取x∈X3，記N（x）∩Y＝｛x1，x2，x3｝．取G2中的5階連通子圖H，使H包含｛x1，x2，x3｝中盡可能多的點且邊數盡可能大．對任意的x′∈｛x1，x2，x3｝＼V（H），由引理3，｜N（x′）∩V（H）｜≤3．而由Y0＝Y1＝Y2＝?，｜N（x′）∩X｜≥3．下證對任意的y∈Y＼（V（H）∪｛x1，x2，x3｝），有｜N（y）∩X｜≥｜N（y）∩V（H）｜．設存在y∈Y＼（V（H）∪｛x1，x2，x3｝），使得｜N（y）∩X｜＜｜N（y）∩V（H）｜．由y與x不相鄰，則｜N（y）∩X｜≥｜N（y）∩N（x）∩X｜＝｜N（y）∩N（x）｜－｜N（y）∩N（x）∩Y｜≥7－3＝4，故｜N（y）∩V（H）｜＝5．記V（H）＝｛x′1，x′2，x′3，y1，y2｝滿足y1，y2｛x1，x2，x3｝．令H′＝G［｛x′1，x′2，x′3，y，y2｝］，則H′是與H包含｛x1，x2，x3｝中一樣多點的5階連通子圖．由y與｛x′1，x′2，x′3，y2｝都相鄰及H的取法，知y1與｛x′1，x′2，x′3，y2｝都相鄰．則邊yy1滿足｜N（y）∩N（y1）｜≥4，與定理條件矛盾！由推論1可得G是λ5－最優(yōu)的．

情形4 Xi＝Yi＝?，i＝0，1，2，3．

取G2中包含盡可能多邊的5階連通子圖H，記V（H）＝｛y1，y2，y3，y4，y5｝．由Y0＝Y1＝Y2＝Y3＝?，對任意的y∈Y，｜N（y）∩X｜≥4．設存在y∈Y＼V（H），使得｜N（y）∩V（H）｜＝5．令H′＝G［｛y1，y2，y3，y4，y｝］，則H′是5階連通子圖．由y與｛y1，y2，y3，y4｝都相鄰及H的取法，知y5與｛y1，y2，y3，y4｝都相鄰．則邊yy5滿足｜N（y）∩N（y5）｜≥4，與定理條件矛盾！故對任意的y∈Y＼V（H），有｜N（y）∩X｜≥｜N（y）∩V（H）｜．由推論1可得G是λ5－最優(yōu)的．定理得證．

［1］ Bondy J A，Murty U S R．Graph Theory with Applications［M］．New York：The Macmillan Press Ltd，1976．

［2］ 呂長虹，張克民．無向de－Bruijn圖的超級邊連通性和限制性邊連通度［J］．應用數學學報，2002，25（1）：29－35．

［3］ Hellwig A，Volkmann L．Sufficient Conditions forλ′－optimality in Graphs of Diameter 2［J］．Discrete Math，2004，283（1－3）：113－120．

［4］ 李建利．三階限制邊連通度的優(yōu)化問題［D］．太原：山西大學，2007．

［5］ Wang S Y，Lin S W，Li C F．Sufficient Conditions for Super k－restricted Edge Connectivity in Grahps of Diameter 2［J］．Discrete Math，2009，309（4）：908－919．

［6］ Wang S Y，Wang R X，Wang X L，et al．Lower Bounds on the Arc－strong Connectivity of Digraphs［J］．山西大學學報：自然科學版，2009，32（4）：516－520．

Neighborhood Intersection Conditions forλ5－Optimal Graphs

ZHANG Guo－zhen，WANG Shi－ying
（School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China）

Neighborhood intersection conditions forλ5－optimal graphs are introduced．Let G be a connected graph with order at least 10．If｜N（u）∩N（v）｜≥6 for all pairs u，v of nonadjacent vertices of G such that neither u nor v lies on a triangle，and｜N（u）∩N（v）｜≥9 for all pairs u，v of nonadjacent vertices of G such that either u or v lies on a triangle，then G isλ5－optimal．If｜N（u）∩N（v）｜≥7 for all pairs u，v of nonadjacent vertices of G，and｜N（x）∩N（y）｜≤3 for all edges xy of G，then G isλ5－optimal．

restricted edge cut；restricted edge connectivity；neighborhood

O157．5

A

0253－2395（2011）02－0176－04

2010－09－20；

2010－12－19

國家自然科學基金（61070229）

張國珍（1978－），女，山西朔州人，在讀博士研究生，講師，研究領域為圖論及其應用．E－mail：guozhen＠sxu．edu．cn