交换折叠超立方体的控制数
The Domination Number of Exchanged Folded Hypercube
DOI: 10.12677/SEA.2017.65012, PDF, HTML, XML,  被引量 下载: 1,331  浏览: 3,535  国家自然科学基金支持
作者: 金 丹, 刘红美, 张艳娟：三峡大学理学院，湖北 宜昌
关键词: 交换超立方体；交换折叠超立方体；控制数；Hamming距离；Exchanged Hypercube； Exchanged Folded Hypercube； Domination Number； Hamming Code
摘要: 交换折叠超立方体 作为超立方体的变体，是在交换超立方体的基础上增加补边形成的。它不仅保留了交换超立方体结构的大部分拓扑特征，而且直径几乎是交换超立方体的一半，有更低的成本因素和恒定的结点度。本文中，我们将进一步研究交换折叠超立方体的性质,并给出了交换折叠超立方体的控制数的一些上界：1)当，有；2)当，有 ；3)
Abstract:  ，其中  。 The exchanged folded hypercube   is an attractive variant of the hypercube and ob-tained by adding some complementary edges from an exchanged hypercube. It not only maintains most of desirable properties of the exchanged hypercube, but also has diameter about half of the exchanged hypercube, and has lower cost factors and constant node degree. In this paper, we will further focus on the properties of exchanged folded hypercube and provide some up bounds for the domination number of exchanged folded hypercube: 1) When  ,   ; 2) When  ,   ; 3) When  ,  , where  .
文章引用：金丹, 刘红美, 张艳娟. 交换折叠超立方体的控制数[J]. 软件工程与应用, 2017, 6(5): 111-119. https://doi.org/10.12677/SEA.2017.65012

参考文献

[1] Xu, J.M. and Ma, M.J. (2006) Edge-Fault-Tolerant Properties of Hypercubes and Folded Hypercubes. Australasian Journal of Combinatorics, 35, 7-16.
[2] Xu, J.M. and Ma, M.J. (2006) Cycle in Folded Hypercubes. Applied Mathematics Letters, 19, 140-145.
https://doi.org/10.1016/j.aml.2005.04.002
[3] Hsieh, S.-Y., Kuo, C.-N. and Huang, H.-L. (2009) 1-Vertex-Fault-Tolerant Cycle Embedding on Folded Hypercubes. Discrete Applied Mathemmatics, 157, 3094-3098.
https://doi.org/10.1016/j.dam.2009.06.012
[4] Yuan, D., Liu, H.M. and Tang, M.Z. (2015) The Connectivity of Faulty Folded Hypercube Networks. 2015 International Conference on Power Electronics and Energy Engineering, 261-265.
[5] Liu, H.M., Tang, M.Z. and Yuan, D. (2016) Some New Results on Fault-Tolerant Cycles Embedding in Folded Hypercubes. Journal of Combinatorial Mathematics and Combinatorial Computing, 97, 23-36.
[6] Yuan, D., Liu, H.M. and Tang, M.Z. (2016) Cycles Embedding in Folded Hypercubes with Faulty Nodes. Annals of Applied Mathematics, 32, 69-78.
[7] 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
[8] Tzeng NF, Wei S. (1991) Enhanced Hypercubes. IEEE Transactions on Computers, 40, 284-294.
https://doi.org/10.1109/12.76405
[9] Qin, R.L. and Liu, H.M. (2015) Cycles Embedding in Conditional Faulty Enhanced Hypercubes. 2015 International Conference on Artificial Intelligence and Industrial Engineering, 233-236.
https://doi.org/10.2991/aiie-15.2015.65
[10] Zhang, Y.J., Liu, H.M. and Liu, M. (2013) Vertex-Fault-Tolerant Cycles Embedding on Enhanced Hypercube Networks. Acta Mathematicae Applicatae Sinica, 33, 1579-1588.
https://doi.org/10.1016/S0252-9602(13)60106-X
[11] Liu, M. and Liu, H.M. (2012) Cycles in Conditional Faulty Enhanced Hypercube Networks. Journal of Communications and Networks, 14, 213-221.
https://doi.org/10.1109/JCN.2012.6253071
[12] Liu, M. and Liu, H.M. (2013) Paths and Cycles Embedding on Faulty En-hanced Hypercube Networks. Acta Mathematica Scientia, 33B, 227-246.
https://doi.org/10.1016/S0252-9602(12)60207-0
[13] Liu, M. and Liu, H.M. (2016) Vertex-Fault-Tolerant Cycle Embedding on Enhanced Hypercube Networks. Acta Mathematicae Applicatae Sinica, English Series, 32, 187-198.
https://doi.org/10.1007/s10255-016-0547-z
[14] Efe, K. (1992) The Crossed Cube Architecture for Parallel Computing. IEEE Transaction on Parallel and Distributed System, 3, 513-524.
https://doi.org/10.1109/71.159036
[15] Hsu, H.S., Fu, J.S. and Chen, G.H. (2007) Fault-Free Hamiltonian Cycle in Crossed Cubes with Conditional Link Faults. Information Sciences, 177, 5664-5674.
https://doi.org/10.1016/j.ins.2007.05.032
[16] Hsu, W.J., Chung, M.J. and Hu, Z. (1996) Gaussian Network for Scalable Distributed Systems. The Computer Journal, 39, 417-426.
https://doi.org/10.1093/comjnl/39.5.417
[17] Tsai, T.-H., Chen, Y.-C. and Tan, J.J.M. (2013) Optimal Edge Congestion of Exchanged Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 27, 250-262.
https://doi.org/10.1109/TPDS.2014.2387284
[18] Loh, P.K.K., Hsu, W.J. and Pan, Y. (2005) The Exchanged Hypercube. IEEE Transactions on Parallel and Distributed Systems, 16, 866-874.
https://doi.org/10.1109/TPDS.2005.113
[19] Ma, M.J. and Liu, B.D. (2009) Cycles Embedding in Exchanged Hypercube. Information Processing Letters, 110, 71-76.
https://doi.org/10.1016/j.ipl.2009.10.009
[20] Li, X.J. and Xu, J.M. (2013) Generalized Measures of Fault Tolerance in Exchanged Hypercubes. Information Processing Letters, 113, 533-537.
https://doi.org/10.1016/j.ipl.2013.04.007
[21] Tsai, T., Chen, Y.C. and Tan, J.J.M. (2014) Topological Properties on the Wide and Fault Diameters of Exchanged Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 25, 3317-3327.
https://doi.org/10.1109/TPDS.2014.2307853
[22] Ma, M. and Zhu, L. (2011) The Super Connectivity of Exchanged Hypercubes. Information Processing Letters, 111, 360-364.
https://doi.org/10.1016/j.ipl.2011.01.006
[23] Qi, H., Li, Y. and Stojmenovic, M. (2015) An Exchanged Folded Hypercube-Based Topology Structure for Interconnection Network. Concurrency and Computation: Practice and Experience, 27, 4194-4210.
https://doi.org/10.1002/cpe.3506
[24] Arumugam, S. and Kala, R. (1998) Domination Parameter of Hypercubes, Journal of the Indian Mathematical Society (N.S), 65, 31-38.
[25] Castro, A., Klavzar, S., Mollard, M. and Rho, Y. (2011) On the Domination Number and the 2-Packing Number of Fibonacci Cubes and Lucas Cubes. Computers and Mathematics with Applications, 61, 2655-2660.
https://doi.org/10.1002/cpe.3506
[26] Fink, J.F., Jacobson, M.S., Kinch, L.F. and Roberts, J. (1985) On Graphs Having Domination Number Half Their Order. Periodica Mathematica Hungarica, 16, 287-298.
https://doi.org/10.1007/BF01848079
[27] Vizing, V.G. (1965) Abound on the External Stability Number of a Graph. Doklady A. N, 164, 729-731.
[28] Klavazr, S. and Ma, M.J. (2014) The Domination Number of Exchanged Hypercube. Information Processing Letters, 114, 159-162.
https://doi.org/10.1016/j.ipl.2013.12.005
[29] Xu, J.M. (2001) Topological Structure and Analysis of Interconnection Network. Kluwer Academic Publishers, Dordrecht/Boston/London.
[30] Jha, P.K. and Slutzki, G. (1995) A Scheme to Construct Distance-Three Codes Using Latin Squares, with Application to the N-Cube. Information Processing Letters, 55, 123-127.
https://doi.org/10.1016/0020-0190(95)00066-L
[31] Jha, P.K. (2015) A Comment on “The Domination Number of Exchanged Hypercubes”. Information Processing Letters, 115, 343-344.
https://doi.org/10.1016/j.ipl.2014.09.016

为你推荐