同阶双轨道连通图的超圈边连通性

姜海宁

(厦门大学数学科学学院,福建厦门 361005)

同阶双轨道连通图的超圈边连通性

姜海宁

(厦门大学数学科学学院,福建厦门 361005)

对于图G,如果G−F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G1;G2;(V1;V2)) 为V轨道图,最小度?(G)≥4,围长g(G)≥6且|V1|=|V2|.假设Gi是ki-正则的,k1≤k2且G1包含一个长度为g的圈,则G是超圈边连通的.

圈边割;圈边连通度;超圈边连通性;轨道

本工作中,规定⁄有的图都是无环和无重边的无向连通图.

互连网络拓扑通常以无向图为数学模型,而图的连通度则是网络容错的一个重要指标.近年来,由于传统的连通度的局限性,人们对连通度的概念进行了推广,如限制性边连通度和圈边连通度等[1-5].

对于无向图G,如果G?F可以使两个圈分离,则称边集F为图G的圈边割.含有圈边割的图称为圈可分图.文献[6-7]刻画了⁄有不含分离圈的多重图,因此本工作考虑到研究圈可分图的性质.Plummer[8]定义了图G的圈边连通度,并且记为λc(G),λc(G)是G中最小圈边割的基数.

圈边连通度在图论的染色、容错及整数流等[9-15]经典领域中起着重要作用.作为网络可靠性的一个重要指标,圈边连通度λc(G)比典型的边连通度具有更高的实用性.

对任意的圈可分图均有λc(G)≤ς(G)(*),其中ς(G)=min{ω(X)},X在G中导出最小圈[16].如果λc(G)=ς(G),则称圈可分图为圈最优的,并记为λc-最优.ω(X)是满足这一条件的所有边的个数,这些边的顶点需要一端在X中,另一端在V(G)X中.

对于任意点集X,G[X]是指X在G中的导出子图.X为X的补集.对于点集X,Y⊆V, [X,Y]G为边集,它的每一条边一端在X中,另一端在Y中.如果[X,X]是最小的圈边割,则G[X]和G[X]都是连通的.如果[X,X]是最小的圈边割,则称点集X为圈边片段.对于基数最小的圈边片段,则称为圈边原子.如果去掉图G中任何一个基数最小的圈边割都会导致其中一个分支是最小圈,则称连通图G是超圈边连通的,记为超-λ[16]c.

设X是一个圈边片段,如果X和X都导不出最小圈,则称X为超圈边片段.基数最小的超圈边片段为超圈边原子[17].在本工作中,用超片段和超原子分别代替超圈边片段和超圈边原子.如果圈边片段可以导出一个圈,则称它是平凡的,否则称为非平凡的.如果X是超片段, 则X也是超片段,且G[X]和G[X]都是连通的.

如果Aut(G)可以在V(G)(E(G))上作用传递,则称图G是点(边)传递的.设x∈V(G),则称集合{xg|g∈Aut(G)}为Aut(G)的一个轨道.显然,Aut(G)分别在每个轨道上作用传递.设图G=(G1,G2,(V1,V2))为连通图,如果Aut(G)分别在V1和V2上作用传递且|V1|=|V2|,则称图G为同阶双轨道连通图.传递图具有高容错性、传递延迟等[18-21]属性,因此在刻画网络拓扑结构时起着重要作用.

Zhou[22]刻画了圈边连通度条件下图的原子.Wang等[16]指出对于任意的最小度δ(G)≥4 且|V|≥6的边传递图是圈最优的.在图的围长g≥5的条件下,k(≥4)-正则点传递图是λc-最优的.Wang等[16]和Zhang等[17]指出最小度δ(G)≥4且|V|≥6的边传递图是λc-最优的.本工作将证明围长≥6的条件下阶数相同的双轨道连通图是超圈边连通的.

1 引理

?理1[17]一个圈最优图不是超圈边连通的充要条件是它有超原子.

2 同阶双轨道图的超-λc5

[1]LATIFI S,HEGDE M,NARAGHI-POUR M.Conditional connectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.

[2]JI S J,MA H P,MA G.The matching energy of graphs with given edge connectivity[J].Journal of Inequalities and Applications,2015,30(1):60-69.

[3]SUN Y F.Generalized 3-edge-connectivity of Cartesian product graphs[J].Czechoslovak Mathematical Journal,2015,65(1):107-117.

[4]CHEKURI C,RUKKANCHANUNT T,XU C.On element-connectivity preserving graph simpli?cation[C]//Lecture Notes in Computer Science.Berlin:Springer-Verlag,2015:313-324.

[5]NING W T.The super connectivity of exchanged crossed cube[J].Information Processing Letter, 2016,116(1):80-84.

[8]PLUMMER M D.On the cyclic connectivity of planar graphs[J].Lecture Notes in Mathematics, 1972,303(6):235-242.

[9]TAIT P G.Remarks on the colouring of maps[J].Proceedings of the Royal Society of Edinburgh, 1880,10(1):501-503.

[10]ROBERTSON N.Minimal cyclic-4-connected graphs[J].Transactions of the American Mathematical Society,1984,284(8):665-684.

[13]ZHANG C Q.Integer flows and cycle covers of graphs[M].New York:Marcel Dekker,1997: 37-45.

[14]HOLTON D A,LOU D J,PLUMMER M D.On the 2-extendability of planar graphs[J].Discret Mathematics,1991,96(2):81-99.

[15]LOU D J,HOLTON D A.Lower bound of cyclic edge connectivity for n-extendability of regular graphs[J].Discrete Mathematics,1993,112(2):139-150.

[16]WANG B,ZHANG Z.On the cyclic edge-connectivity of transitive graphs[J].Discrete Mathematics,2009,309(6):4555-4563.

[17]ZHANG Z,WANG B.Super cyclically edge-connected transitive graphs[J].Journal of Combinatorial Optimization,2011,22(4):549-562.

[18]MENG J X.Optimally super-edge-connected transitive graphs[J].Discrete Mathematics,2003, 260(1):239-248.

[19]XU J M.On conditional edge-connectivity of graphs[J].Acta Mathematicae Applicatae Sinica, 2002,16(4):414-419.

[21]XU J M,LIU Q.2-restricted edge-connectivity of vertex-transitive graphs[J].Australas J Combin,2004,30(5):41-49.

[22]ZHOU J X.Atoms of cyclic edge connectivity in regular graphs[J].Journal of Combinatorial Optimization,2016,31(1):382-395.

[23]LIN H Q,YANG W H,MENG J X.On cyclic edge connectivity of graphs with two orbits of same size[J].Journal of Mathematical Study,2010,43(3):1-9.

[24]TINDELL R.Connectivity of Cayley graphs[M].Boston:Springer-Verlag,1996:41-64.

Super cyclically edge connected graphs with two orbits of the same size

JIANG Haining
(School of Mathematical Sciences,Xiamen University,Xiamen 361005,Fujian,China)

For a graph G,an edge set F is a cyclic edge-cut if(G−F)is disconnected and at least two of its components contain cycles.If G has a cyclic edge-cut,it is said to be cyclically separable.The cyclic edge-connectivity is cardinality of a minimum cyclic edgecut of G.A graph is super cyclically edge-connected if removal of any minimum cyclic edge-cut makes a component a shortest cycle.Let G=(G1;G2;(V1;V2))be a doubleorbit graph with minimum degree?(G)≥4,girth g≥6 and|V1|=|V2|.Suppose Giis ki-regular,k1≤k2and G1contains a cycle of length g,then G is super cyclically edge connected.

cyclic edge-cut;cyclic edge-connectivity;super cyclically edge-connected; orbit

1007-2861(2017)02-0252-05

10.3969/j.issn.1007-2861.2016.05.004

2016-03-23

国家自然科学基金资助项目(11471273)

通信?者:姜海宁(1983|),男,博士研究生,研究方向为图论.E-mail:hnjiangsd@163.com