Super Cyclically Edge Connected Half Vertex Transitive Graphs

Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.

最大边连通和super-边连通超图的充分条件

设H是连通超图。若超图H的边连通度等于其最小度,则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成,则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次,给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了D ankelmann和Volkmann(1997)以及Hellwig和Volkmann(2005)在图上的相关结论。

Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.

Super Cyclically Edge-connected Vertex-transitive Graphs of Girth at Least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.： Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549–562 （2011）], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.

Super Edge-connectivity and Zeroth-order General Randi Index for -1≤α< 0

Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randic index R_α-0（G） =Σ x∈V（G） d_G-α（x）, where dG（x） denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randic index for -1 ≤α 〈 0, respectively.

Super-Edge-Connectivity of G(k,d,s)(s≥k/2)

A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.

直径为2的图的超级边连通性质

Ｍ．Ａ．Ｆｉｏｌ在１９９２年给出了直径为２的无向简单图是超级边连通的三个充分条件（Ｆ１）、（Ｆ２）和（Ｆ３）．本文证明了：（１）条件（Ｆ１）也是必要条件，从而得到直径为２的图是超级边连通图的特征刻画；（２）（Ｆ３）（Ｆ２）（Ｆ１），但（Ｆ１）／（Ｆ２）／（Ｆ３）；（３）条件（Ｆ３）可进一步保证图是最优超级边连通的，但（Ｆ２）不能．这里的最优超级边连通的概念是通过限制性边连通度自然地定义的．最后提出两个有关的待解决的问题．

图是超级限制性边连通的一个Ore型充分条件

设 G是 n阶简单无向图 ,G的顶点 x的度记为 d(x) .证明了如果对 G中每一对不相邻的顶点 x和 y都有 d(x) +d(y)≥ n+2 ,那么 ,G是超级限制性边连通的 ,除非 n≥ 6是偶数且 G=2 Kn/2 ∪ F2 ,这里 F2 是 G的一个 2因子 .这一结果是对图的极大限制性边连通性的 Ore型充分条件的进一步扩展 .

半传递重图的限制性边连通度（英文）

设G=(V,E)是一个重图(包含重边,但不含环).图G的边连通度,记为λ(G),是G的最小边割的基数.我们称G是极大边连通的如果λ(G)=δ(G);称图G是超边连通的如果每个最小边割都是某个点的邻边集合.图G的限制性边连通度,记为λ(G),是图G的最小限制性边割的基数.如果λ(G)达到限制性边连通度的上界,我们称G是λ-最优的.一个二部重图是半传递的如果它作用在每个部分上都是传递的.在本文中,我们将刻画极大边连通的、超边连通的、λ-最优的半传递重图.

变换图G^(--+)的超边连通性

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G--+都是极大边连通的,G--+是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.

变形超立方体网络的可靠性分析(英文)

作为超立方体网络的变形,n维变形超立方体VQn是Cheng和Chuang于1994年提出来的,它具有许多超立方体所具有的优良性质,比如正则性和递归结构.证明了:VQn的连通度和边连通度都等于n,限制连通度和限制边连通度都等于2n-2.这个结果意味着,为了使VQn不连通且不含孤立点,至少有2n-2个点或者边要同时发生故障.

交换交叉立方网络的可靠性研究

针对传统的基于连通度分析交换交叉立方网络可靠性的方法的不足,提出一种基于超连通度的可靠性分析方法,因为用超连通度衡量互连网络的稳定性和容错能力较之用连通度更为准确。在研究了交换交叉立方网络的拓朴结构的基础上证明了交换交叉立方网络的点连通度和边连通度均是s+1(s≤t),证明了交换交叉立方网的超点连通度和超边连通度均是2s(s≤t),也就是说,当移除交换交叉立方网络的2s个点或者2s条边,会得到不包括孤立点的非连通图。当交换交叉立方网络被用来构建大型并行计算/通信系统时,运用上述成果能够更加准确地为系统的稳定性和容错能力提供支持。

图是超级λ_k-连通(k=4,5)的一个Ore型充分条件

图的k阶限制边连通度λk(G)对衡量网络可靠性起重要的作用.本文给出图是超级λk(k=4,5)连通的一个Ore型条件.

变换图G^(++-)的超力连通性(英文)

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G++-都是超边连通的.

无向Kautz图的超级限制边连通性(英文)

限制边连通度作为边连通度的推广,是计算机互连网络可靠性的一个重要度量.Superλ-′是比限制边连通度更精确的一个网络可靠性指标.一个图是Superλ-′的,如果它的任一最小限制边割都孤立一条有最小边度的边.本文考虑一类重要的网络模型-无向K autz图UK(d,n)的限制边连通度λ,′证明了当d 3,n 2时,λ(′UK(d,n))=4d-4,并进一步指出此时的UK(d,n)是Superλ-′的.

有向图和二部有向图的局部边连通性

笔者首先利用顶点的度和给出了有向图是超级局部边连通的一个最好可能的充分条件,然后提出了二部有向图为极大局部边连通和超级局部边连通的度序列条件.这些结果在网络可靠性分析中有一定应用.

极大局部边连通和超级局部边连通二部有向图的邻域条件

本文主要证明了对于n阶二部有向图D,当最小度δ≥3,对任意同部顶点x,y,有min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}≥n+3/4时,D为极大局部边连通的;当最小度δ≥4,对任意同部顶点x,y,有min{|N+(x)∪N+(y)|,|N-(x)∪N-(y)|}>n/4+1时,D为超级局部边连通的。我们证明了条件的最好可能性及结果与原有结果的独立性。

图是λ_3-最优和超级-λ_3的范型条件

设G是有限简单无向图,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。G的k-限制边连通度λk(G)是G的k-限制边割之中最少的边数。定义ξk(G)=min{[U,U-]:U V(G),|U|=k,G[U]是连通的},若λk(G)=ξk(G),则称G是λk-最优的。若任意最小k-限制边割都孤立一个k阶分支,则称图G是超级-λk的。应用范型条件给出了图是λ3-最优和超级-λ3的充分条件。

图是λ′最优和超级λ′的充分条件

设G是有限简单无向图,使G-S的每个分支都不含孤立的边割S称为G的限制边割。G的限制连连通度λ′(G)是G的限制边割之中最少的边数,定义ξ(G)=min{d(x)+d(y)-2;xy∈E(G)}为G的最小边度。如果λ′(G)=ξ(G),则称G是λ′最优的。若任意最小限制边割都弧立一边,则称图G是超级λ′的。应用范型度条件给出了图是λ′最优和超级λ′的令分条件。