λ5－最优图的邻域交条件

张国珍，王世英

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

λ5－最优图的邻域交条件

张国珍，王世英

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

给出了λ5－最优图的邻域交条件：设G是一个阶至少为10的连通图，对G中任意一对不相邻顶点u和v，若u，v均不在三角形中，有｜N（u）∩N（v）｜≥6，若u或v在三角形中，有｜N（u）∩N（v）｜≥9，则G是λ5－最优的；若G中任意一对不相邻顶点u和v满足｜N（u）∩N（v）｜≥7，任意一条边xy满足｜N（x）∩N（y）｜≤3，则G是λ5－最优的．

限制边割；限制边连通度；邻域

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］．

多处理机的互连网络拓扑通常以图为数学模型，这时图的顶点代表处理机，而一对处理机之间的直接通信联系则用连接这对顶点的边来表示，因此网络拓扑的性能可以通过图的性质和参数来度量［2－6］．在设计和选择互联网络拓扑结构时，要考虑的一个问题是系统的可靠性能．边连通度是度量网络可靠性的一个重要参数．不过，这个参数也有一些缺陷，比如：它不能准确反映由于信关的损坏而造成的系统损坏程度，也不能处理某些部分不会同时损坏的网络的可靠性［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－最优的．在λk－最优图的邻域交条件方面，已有：

定理1［3］设G是阶至少为4的一个连通图，对G中任意一对不相邻顶点u，v，若u，v均不在三角形上，有｜N（u）∩N（v）｜≥2，若u或v在三角形上，有｜N（u）∩N（v）｜≥3，则G是λ2－最优的．

定理2［4］设G是一个λ3－连通图，对G中任意一对不相邻顶点u，v，若u，v均不在三角形上，有｜N（u）∩N（v）｜≥4，若u或v在三角形上，有｜N（u）∩N（v）｜≥5，则G是λ3－最优的．

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－最优的．

以下考虑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－最优的．特别地，若对任意的x∈X＼V（H），有｜N（x）∩Y｜≥5，则G是λ5－最优的．

引理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条边相关联的点集．XiX，YiY定义为X，Y的与S中恰好i条边相关联的点集（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－最优的．

证明 由引理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－最优的．下设｜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－最优的．

情形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－最优的．下设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－最优的．

情形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－最优的．

情形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－最优的．定理得证．

定理4 设G是一个阶至少为10的连通图，若G中任意一对不相邻顶点u和v满足｜N（u）∩N（v）｜≥7，任意一条边xy满足｜N（x）∩N（y）｜≤3，则G是λ5－最优的．

证明 由引理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－最优的．下设｜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－最优的．

情形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－最优的．以下假设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－最优的．

情形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－最优的．

情形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－最优的．定理得证．

［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］ 李建利．三阶限制边连通度的优化问题［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