Kautz图的限制边连通度

限制边连通度是对传统边连通度的推广 ,而且是计算机互连网络容错性的一个重要度量 .本文考虑两类重要的网络模型———Kautz有向图K(d ,n)和Kautz无向图UK(d ,n)的限制边连通度λ′,并得到如下结果 :除了λ′(K( 2 ,1) )不存在外 ,均有λ′(K(d ,n) ) =2d-2 ;当d≥ 3 ,n≥ 3时 ,4d-5≤λ′(UK(d ,n) ) ≤ 4d -4 .     

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比de Bruijn网络有更好的限制边连通性.     

一类无向Kautz图的k限制边连通度的上界

在Moor-Shannon网络模型中,k限制边连通度较大的网络一般有较好的可靠性和容错性.本文在无向Kautz图UK(2,n)中研究k限制边连通度的上界ξk,证明了ξ5(UK(2,3))=6,ξ5(UK(2,n))=8,n≥4,且当4≤k≤n时,ξk(UK(2,n))≤2(k-「k/3」).     

点可迁图的限制边连通度

设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.     

无向de-Bruijn图的超级边连通性和限制性边连通度

super-λ和限制性边连通度是两个比边连通度更能刻画网络可行性的参数。本文证明了无向无向de-Bruijn图UB（d,n)是super-λ（d≥2,n≥2)。对n≥4，我们证明了UB（2,n)的限制性边连通度为4；UB（2，3）的限制性边连通度是3。对d≥3我们指出UB(d,n)(n≥3)的限制性连连通度λ‘，满足2d-2λ‘≤4d-4。     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1).     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.     

REFINED CONNECTIVITY PROPERTIES OF ABELIAN CAYLEY GRAPHS

1.IntroductionAgraphG=(V,E)meansafinitegraphwithoutloopsandmultipleedgeswithvertexsetVandedgesetE,theclassicaledgeconnectivityA(G)ofGistheminimumsizeofasetUofedgessuchthatG--Uisdisconnected,andsuchasetUiscalledaoutsetofG.Notethatintheabovedefinition,absolutelynoconditionsorrestrictionsareimposedeitheronthecomponelltsofG--UoronthesetU.ThusitwouldseemnaturaltogeneralizetheconceptofedgeconnectivitybyintroducingsomeconditionsorrestrictionsonthecomponentsofG--Uand/orthesetU.Asageneralizatio…     

围长为3的点可迁图的3限制边连通度

设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4.     

网络连通性的最优化

简述了极大边连通图和超边连通图;限制边连通度、极大限制边连通图和超限制边连通图的研究进展.     

On 3-restricted edge connectivity of undirected binary Kautz graphs

An edge cut of a connected graph is m-restricted if its removal leaves every component having order at least m. The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connectivity. It is known that when m≤4, networks with maximal m-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge.     

Sufficient conditions for λ′‐optimality in graphs with girth g

For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) ? 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g ? 1, g being the girth of the graph, and show that a graph G with diameter at most g ? 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.