同階雙軌道連通圖的超圈邊連通性

姜海寧

(廈門大學數學科學學院,福建廈門 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是超圈邊連通的.

圈邊割;圈邊連通度;超圈邊連通性;軌道

本工作中,規(guī)定?有的圖都是無環(huán)和無重邊的無向連通圖.

互連網絡拓撲通常以無向圖為數學模型,而圖的連通度則是網絡容錯的一個重要指標.近年來,由于傳統(tǒng)的連通度的局限性,人們對連通度的概念進行了推廣,如限制性邊連通度和圈邊連通度等[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),則稱圈可分圖為圈最優(yōu)的,并記為λc-最優(yōu).ω(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的邊傳遞圖是圈最優(yōu)的.在圖的圍長g≥5的條件下,k(≥4)-正則點傳遞圖是λc-最優(yōu)的.Wang等[16]和Zhang等[17]指出最小度δ(G)≥4且|V|≥6的邊傳遞圖是λc-最優(yōu)的.本工作將證明圍長≥6的條件下階數相同的雙軌道連通圖是超圈邊連通的.

1 引理

?理1[17]一個圈最優(yōu)圖不是超圈邊連通的充要條件是它有超原子.

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