计算机科学与应用  >> Vol. 7 No. 10 (October 2017)

基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质
Based on FQn and Cycles Cell-Breeding Network FQCC(n,k) and Its Properties

DOI: 10.12677/CSA.2017.710109, PDF, HTML, XML, 下载: 1,096  浏览: 1,319 

作者: 赵 媛, 师海忠*:西北师范大学数学与统计学院,甘肃 兰州

关键词: 折叠立方体连通圈网络FQCC(nk)平面图Hamilton图Hamilton连通图点可迁的The Folded Cube-Connected Cycles FQCC(nk) Planar Graph Hamilton Graph Hamilton-Connected Graph Vertex-Transitive

摘要: 折叠立方体连通圈网络FQCC(n) (n > 1)是一类典型的互连网络,它是3正则的。师海忠根据折叠立方体连通圈网络i>FQCC(n) (n > 1)和细胞分裂生长图模型设计出了一种新的互连网络——FQCC(n,k) (n > 1,k是非负整数):用三长的圈代替FQCC(n)的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络FQCC(n) (n > 1)中与该顶点关联的一条边上,得到新的网络FQCC(n,1);再类似的用三长的圈代替FQCC(n,1)的每个顶点得FQCC(n,2),循环执行上述方法k次得到的新网络称为FQCC(n,k) (n > 1,k是非负整数)。该网络FQCC(n,k)在保持了FQCC(n)的小的固定的度(为3)的特性外,还有比FQCC(n)更好的扩展性。进而提出了猜想:FQCC(n,k)是Hamilton图。赵媛证明了FQCC(2,k)是平面图和Hamilton图,还证明了FQCC(n,k) (k > 1)不是点可迁的。
Abstract: The folded cube-connected cycles network FQCC(n) (n > 1) is a classic interconnection network; it is 3 regular. On the basis of the folded cube-connected cycles network FQCC(n) (n > 1) and cell- breeding graph model for interconnection network, FQCC(n,k) (n > 1, k is not a negative integer) is designed by Haizhong Shi: each vertex in the folded cube-connected cycles network FQCC(n) (n > 1) is replaced by the cycles of length 3, and the vertex in every cycle is located on the edge of the folded cube-connected cycles connected to the vertex, then we called the new network FQCC(n,1); in similar way each vertex in the folded cube-connected cycles network FQCC(n,1) (n > 1) is replaced by the cycles of length 3, then we called the new network FQCC(n,2), looping execution the above method k times, and then get the new network—FQCC(n,k) (n > 1, k is not a negative integer). The network FQCC(n,k) keeps small or fixed degree (is 3) of FQCC(n), and has better extendability than FQCC(n). Furthermore proposed a conjecture: FQCC(n,k) is Hamiltonian. Yuan Zhao proofs that FQCC(2,k) is planar and Hamiltonian, and that FQCC(n,k) (k > 1) is not vertex- transitive.

文章引用: 赵媛, 师海忠. 基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质[J]. 计算机科学与应用, 2017, 7(10): 960-973. https://doi.org/10.12677/CSA.2017.710109

参考文献

[1] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2013.
[2] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, London.
https://doi.org/10.1007/978-1-84628-970-5
[3] Cheng, E., Connolly, R. and Melekian, C. (2015) Matching Preclusion and Conditional Matching Preclusion Problems for the Folded Petersen Cube. Theoretical Computer Science, 576, 30-44.
https://doi.org/10.1016/j.tcs.2015.01.046
[4] El-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42.
https://doi.org/10.1109/71.80187
[5] Zhu, Q. and Xu, J.M. (2006) On Restricted Edge Connectivity and Extra Edge Connectivity of Hypercubed and Folded Hypercubes. Journal of University of Science and Technology of China, 36, 249-253.
[6] Wang, Y.H. and Xu, J.M. (2005) Minimum Feedback Vertex Set in Folded Hypercubes. Operations Research and Management Science, 14, 8-11.
[7] Ma, M.J., Xu, J.M. and Du, Z.Z. (2004) Edge-Fault-Tolerant Bipanconnectivity of Hypercubes and Edge-Fault-Tolerant Edge-Pancyclicity of Folded Hypercubes. Proceeding of the Seventh National Conference of Operations Research Society of China, 1261-1267.
[8] 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]. 北京: 中国运筹学会第十一届学术交流会文集, 2010: 202-208.
[9] Shi, H.Z. and Shi, Y. (2015) A New Model for Interconnection Network: k-Hierarchical Ring and r-Layer Graph Network.
http://vdisk.weibo.com/s/dlizJyferZ-Zl
[10] Shi, H.Z. and Shi, Y. (2015) Cell-Breading Graph Model for Interconnection Networks.
http://vdisk.weibo.com/s/dlizJyfesb05y
[11] Shi, H. and Shi, Y. (2015) A Hierarchical Ring Group-Theoretic Model for Interconnection Networks.
http://vdisk.weibo.com/s/dlizJyfeBX-2J
[12] 师海忠, 常立婷, 赵媛, 张欣, 王海锋. 2r-正则图连通圈网络的Hamilton分解[J]. 计算机科学, 2016, 43(11A), 304-307 + 319.
[13] Sebastian, M.P., Nagendra Rao, P.S. and Jenkins, L. (1998) Properties and Performance of the Folded Cube-Connected Cycles. Journal of Systems Architecture, No. 44, 359-374.
[14] Hsu, L.-H., Ho, T.-Y., Ho, Y.-H. and Tsay, C.-W. (2014) Cycles in Cube-Connected Cycles Graphs. Discrete Applied Mathematics, No. 167, 163-171.
[15] Chen, X.-B. (2009) Some Results on Topological Properties of Folded Hypercubes. Information Processing Letters, No. 109, 395-399.
[16] 师海忠, 常立婷. 推广立方连通圈网络的Hamilton分解的算法[J]. 计算机科学与应用, 2016, 6(9): 573-582.
[17] 师海忠, 赵媛. 推广折叠立方体连通圈网络的Hamilton分解的算法[J]. 计算机应用研究, 2017.