m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm(G).对于包含m-限制边割的连通图G,有λm(G)≤ξm(G)(m≤3);如果λm(G)=ξm(G),则称图G是极大m-限制边连通的.本文证明:当n≥7时,无向广义De Bruijn图UBG(2,n)是极大m-限制边连通的(m={2,3}).

An m-restricted edge cut is an edge cut of a connected graph that disconnects this graph into each components having order at least m.The minimum size m-restricted edge cut of graph G is m-restricted edge connectivity,denoted by λm（G）.It is known that λm（G） ≤ ξm（G） holds for graph G that contain m-restricted edge cut whenever m ≤ 3.Graph G is maximally m- restricted edge connected if λm（G）=ξ m（G）.In this paper,for some m = { 2,3},undirected generalized De Bruijn graphs UBG（2,n） are proved to be maximally m-restricted edge connected whenever n ≥ 7.

设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ''(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ''-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ''-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ''-最优的。最后给出例子说明这些结果给出的边界都是紧的。

An edge cut S of a connected graph G is called as a restricted edge cut,if G-S contains unisolated verti-ces. The minimum cardinality of all restricted edge cuts is called as the restricted edge connectivity of λ''( G). A graph G is optimally restricted edge-connected,for shortλ''-optimal,ifλ''( G)=ξ( G),whereξ( G)is the minimum edge degree of G. A graph is thought to be super-restricted edge-connected,for short super-λ'' if every minimum re-stricted edge cut isolates an edge. Let G be a connected triangle-free graph of order n and minimum degree δ( G≥2),if the minimum edge degree ξ(G)≥ n( 2-2) 1+(δ 1G)-( 1),then G is λ''-optimal. Using this result,we deduce that if the minimum degree of triangle-free graph G,δ( G)≥n4 +1,then G is λ''-optimal. Finally,an example is presented to show that the bounds of these results are both tight.

传统的GN算法每次迭代删除一条边,时间复杂度高,其变种时间复杂度有所下降,但分割精度也有待于提高;在复杂网络图中,图的连通性是由拉普拉斯矩阵的第二小特征值决定的,通过最小化网络连通性,提出了贪婪谱优化割边模型,该模型在GN算法基础上,一次删除多条边,为避免出现边过度分割,每条边设置了权重;为了进一步降低时间复杂度,选择网络代数连通性下降最快的边进行删除,提出了基于边中心性测度的割边模型,与传统的利用最短距离和随机游走不同,模型采取谱分析方法对每条边定义边中心性测度,速度更快,分割精度能到达要求,适合处理中规模社区结构。

The GN algorithm removes one edge with the highest betweenness at each iteration. It has relatively high time complexity. Although the time complexity of variations on GN is reduced, the calculation accuracy needs to be improved. In complex network graph, the second smallest eigenvalue of Laplacian matrix is the algebraic connectivity. It presents greedy spectral optimal cut model by minimizing the algebraic connectivity of complex network. The model cuts k edges at an iteration based on GN algorithm. To avoid edges overcutting, the weight is set up for each edge. It proposes edge cen-trality cut model in order to reduce the time complexity further, which is different from the shortest distance and random walking methods. The model calculates edge centrality by the spectral analysis and can be used in medium-size networks with higher efficiency and accuracy.

如果G－F不连通且每个连通分支至少含有两个顶点，则连通图G的边子集F称为限制边割。如果图G的每个最小限制边割都孤立G中的一条边，则称G是超限制边连通的（简称超λ′）。对于满足｜F｜≤ m的任意子集 F? E（G），超λ′图G的边容错性ρ′（G）是使得G－F仍是超λ′的最大整数m 。这里给出了min｛k1＋ k2－1，υ1 k2－2 k1－2 k2＋1，υ2 k1－2 k1－2 k2＋1｝≤ρ′（G1× G2）≤ k1＋ k2－1，其中，对每个 i∈｛1，2｝，G i是阶为υi 的k i正则k i边连通图且k i≥4，G1× G2是G1和G2的笛卡尔乘积。并给出了使得ρ′（G1× G2）＝ k1＋ k2－1的一些充分条件。

A subset F of edges in a connected graph G is a restricted edge‐cut if G - F is disconnected and every component has at least two vertices .A graph G is super restricted edge‐connected (super‐λ′for short ) if every minimum restricted edge‐cut of G isolates at least one edge .The edge fault‐tolerance ρ′(G) of a super‐λ′graph G is the maximum integer m for which G-F is still super‐λ′for any subset F? E(G) with |F|≤ m .It was shown that min{k1 + k2 -1 ,υ1 k2 -2 k1 -2 k2 + 1 ,υ2 k1 -2 k1 -2 k2 + 1} ≤ ρ′(G1 × G2 ) ≤ k1 + k2 -1 , w here Gi is a ki‐regular ki‐edge‐connected graph of order υi with ki ≥ 4 for each i∈ {1 ,2} and G1 × G2 is the Cartesian product graph of G1 and G2 .And some sufficient conditions such thatρ′(G1 × G2 )= k1 + k2 -1 w ere presented .

可靠性评估对于多处理系统的设计和维护占据重要的地位．在众多的可靠性评价系统方法中，外边连通度（也称限制性边连通度）是其中重要的一种．对于一个正整数h，如果图G的边集合S，满足G—s是不连通的，并且每一个连通分支至少有h个点，则称S是图G的h-外边割．称h-外边割S最小的基数为图G的h-外边连通度，记为λh（G）．文章给出了n维超立方体Qn的h-外边连通度λh（G），其中正整数n≥7，2「n/2」＋1≤h≤2「n/2」＋2.

Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The extra edge-connectivity ( also restricted edge connectivity) is a kind of measure for the reliability of interconnection systems. For a given positive integer h, an edge set S of a connected graph G is called as a h-extra edge-cut, if G-S is no longer connected, and each component of G-S has at least h vertices. The cardinality of a minimum h-extra edge-cut, is the h-extra edge-connectivity of G, denoted byλh(G). Let n be a positive integer, n≥7. In this paper, we determine the h-extra edge-connectivity of n-dimensional hypercubeλh(Qn) for 2b n2 c+1≤h≤2b n2 c+2.