由2-树生成的Cayley图的容错极大局部连通性
|
摘要
主要证明了由2-树生成的Cayley图A_n(Δ)(n≥5)是(2n-7)容错极大局部连通和一对多(2n-7)容错极大局部连通。限制每个顶点有至少3个无故障邻点,则A_n(Δ)(n≥5)是(4n-15)容错极大局部连通。
It was shown that Cayley graphs A_n( Δ) generated by 2-trees is( 2 n-7)-fault-tolerant maximally local connected for n ≥ 5 and is also( 2 n-7)-fault-tolerant one-to-many maximally local-connected for n≥5. Furthermore,under the restricted condition that each vertex has at least three fault-free adjacent vertices,Cayley graphs A_n( Δ) generated by 2-trees is( 4 n-15)-fault-tolerant maximally local connected for n≥5.
It was shown that Cayley graphs A_n( Δ) generated by 2-trees is( 2 n-7)-fault-tolerant maximally local connected for n ≥ 5 and is also( 2 n-7)-fault-tolerant one-to-many maximally local-connected for n≥5. Furthermore,under the restricted condition that each vertex has at least three fault-free adjacent vertices,Cayley graphs A_n( Δ) generated by 2-trees is( 4 n-15)-fault-tolerant maximally local connected for n≥5.
引文
[1] BEINEKE L W,PIPPERT R E. The number of labeled k-dimensional trees[J]. Journal of Combinatorial Theory,1969,6(2):200-205.
[2] BONDY J A,MURTY U S R. Graph theory[M]. London:Springer,2008.
[3] SHIH L M,CHIANG C F,HSU L H,et al. Strong Menger connectivity with conditional faults on the class of hypercubelike networks[J]. Information Processing Letters,2008,106(2):64-69.
[4] YANG W,ZHAO S,ZHANG S. Strong Menger connectivity with conditional faults of folded hypercubes[J]. Information Processing Letters,2017,125:30-34. DOI:10. 1016/j. ipl. 2017. 05. 001.
[5] OH E,CHEN J. On strong Menger-connectivity of star graphs[J]. Discrete Applied Mathematics,2003,129(2):499-511. DOI:10. 1016/S0166-218X(02)00600-5.
[6] SHIH L M,TAN J M. Fault-tolerant maximal local-connectivity on the Bubble-sort graphs[C]//Sixth International Conference on Information Technology:new generations. Las Vegas:IEEE Computer Society,2009:564-569.
[7] SHIH L M,CHIANG C F,HSU L H,et al. Fault tolerant maximal local connectivity on Cayley graph generated by transposition tree[J]. Journal of Interconnection Networks,2009,10(3):253-260.
[8] CAI H,LIU H,LU M. Fault-tolerant maximal local-connectivity on bubble-sort star graphs[J]. Discrete Applied Mathematics,2015,181:33-40. DOI:10. 1016/j. dam. 2014. 10. 006.
[9] ZHOU S,CHEN L. Fault tolerant maximal local connectivity of alternating group networks[C]//IEEE. International Congress on Image and Signal Processing. Yantai:IEEE,2010:4394-4398.
[10] MENGER K. Zur allgemeinen kurventheorie[J]. Fund Math,1927,10(1):96-115.
[11] OH E,CHEN J. On strong fault tolerance:parallel routing in star networks with faults[J]. Journal of Interconnection Networks,2003,4(1):113-126.
[12] CHENG E,LIPTAK L,YANG W,et al. A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees[J]. Information Sciences,2011,181(19):4300-4308. DOI:10. 1016/j. ins. 2011. 05. 010.
[13] CHENG E,LIPTAK L,SALA F. Linearly many faults in 2-tree-generated networks[J]. Networks,2010,55(2):90-98. DOI:10. 1002/net. 20319.
[14] PIPPERT R E. Properties and characterizations of k-trees[J]. Mathematika,1971,18(1):141-151.
[15] VOLKMANN L. On local connectivity of graphs[J]. Applied Mathematics Letters,2008,21(1):63-66. DOI:10.1016/j. aml. 2006. 12. 014.
[2] BONDY J A,MURTY U S R. Graph theory[M]. London:Springer,2008.
[3] SHIH L M,CHIANG C F,HSU L H,et al. Strong Menger connectivity with conditional faults on the class of hypercubelike networks[J]. Information Processing Letters,2008,106(2):64-69.
[4] YANG W,ZHAO S,ZHANG S. Strong Menger connectivity with conditional faults of folded hypercubes[J]. Information Processing Letters,2017,125:30-34. DOI:10. 1016/j. ipl. 2017. 05. 001.
[5] OH E,CHEN J. On strong Menger-connectivity of star graphs[J]. Discrete Applied Mathematics,2003,129(2):499-511. DOI:10. 1016/S0166-218X(02)00600-5.
[6] SHIH L M,TAN J M. Fault-tolerant maximal local-connectivity on the Bubble-sort graphs[C]//Sixth International Conference on Information Technology:new generations. Las Vegas:IEEE Computer Society,2009:564-569.
[7] SHIH L M,CHIANG C F,HSU L H,et al. Fault tolerant maximal local connectivity on Cayley graph generated by transposition tree[J]. Journal of Interconnection Networks,2009,10(3):253-260.
[8] CAI H,LIU H,LU M. Fault-tolerant maximal local-connectivity on bubble-sort star graphs[J]. Discrete Applied Mathematics,2015,181:33-40. DOI:10. 1016/j. dam. 2014. 10. 006.
[9] ZHOU S,CHEN L. Fault tolerant maximal local connectivity of alternating group networks[C]//IEEE. International Congress on Image and Signal Processing. Yantai:IEEE,2010:4394-4398.
[10] MENGER K. Zur allgemeinen kurventheorie[J]. Fund Math,1927,10(1):96-115.
[11] OH E,CHEN J. On strong fault tolerance:parallel routing in star networks with faults[J]. Journal of Interconnection Networks,2003,4(1):113-126.
[12] CHENG E,LIPTAK L,YANG W,et al. A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees[J]. Information Sciences,2011,181(19):4300-4308. DOI:10. 1016/j. ins. 2011. 05. 010.
[13] CHENG E,LIPTAK L,SALA F. Linearly many faults in 2-tree-generated networks[J]. Networks,2010,55(2):90-98. DOI:10. 1002/net. 20319.
[14] PIPPERT R E. Properties and characterizations of k-trees[J]. Mathematika,1971,18(1):141-151.
[15] VOLKMANN L. On local connectivity of graphs[J]. Applied Mathematics Letters,2008,21(1):63-66. DOI:10.1016/j. aml. 2006. 12. 014.