广义b-基超立方体网络的控制数
Domination Numbers for Generalized Base-b Hypercube Networks
DOI: 10.12677/CSA.2017.79093, PDF, HTML, XML,  被引量 下载: 1,628  浏览: 4,527 
作者: 师海忠*, 杨进霞：西北师范大学数学与统计学院，甘肃 兰州
关键词: 广义b-基超立方体网络；NPC问题；控制数；Generalized Base-b Hypercube Network； NPC Problem； Domination Number
摘要: 控制数是刻画容错网络中资源共享可靠性的一个参数。确定网络的控制数是NPC问题。Lakshmivarahan, Dhall提出了著名的互连网络—广义b-基超立方体网络。该文给出了当b=3,n=2,3,4 时广义b-基超立方体网络控制数的具体值，以及当5≤n≤8 时控制数的界；进一步提出了两个问题和与该问题相对应的两个猜想。
Abstract: Domination number is a parameter to describe the reliability of resource sharing in a fault-tole- rant network. Determining the domination numbers of a graph is a NPC problem. Generalized base-b hypercube has been put forward by Lakshmivardhan and Dhall, which is a famous inter-connection network. In this paper, we study the exact values of the domination numbers of generalized base-b hypercube for b=3,n=2,3,4 and the bounds of the domination numbers for 5≤n≤8. Furthermore, two problems and two conjectures with the problems are proposed.
文章引用：师海忠, 杨进霞. 广义b-基超立方体网络的控制数[J]. 计算机科学与应用, 2017, 7(9): 814-819. https://doi.org/10.12677/CSA.2017.79093

参考文献

[1] 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.
[2] Lakshmivarahan, S. and Dhall, S.K. (1988) A New Hierarchy of Hypercube Interconnection Schemes for Parallel Computers. Journal of Supercomputing, 2, 81-108.
https://doi.org/10.1007/BF00127849
[3] Huang, C.-H. and Fang, J.-F. (2008) The Pancyclicity and the Hamiltonian-Connectivity of the Generalized Base-b Hypercube. Computers and Electrical Engineering, 34, 263-269.
https://doi.org/10.1016/j.compeleceng.2007.05.011
[4] Akers, S.B., Harel, D. and Krishnamurthy, B. (1987) The Star Graph: An Attractive Alternative to the n-Cube. Proceeding of the 1987 International Conference on Parallel Process, The Pennsylvania University Press, Philadelphia, 393-400.
[5] Akers, S.B. and Krishnamurthy, B. (1989) A Group-Theoretic Model for Symmetric Interconnection Networks. IEEE Transactions on Computers, 38, 555-565.
https://doi.org/10.1109/12.21148
[6] 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
[7] 师海忠. 互连网络的代数环模型[D]: [博士学位论文]: 北京: 中国科学院应用数学研究所, 1998.
[8] Efe, K. (1991) A Variation on the Hypercube with Lower Diameter. IEEE Transactions on Computer, 40, 1312-1316.
https://doi.org/10.1109/12.102840
[9] Cull, P. and Larson, S.M. (1995) The Mӧbius Cube. IEEE Transactions on Computer, 44, 647-659.
https://doi.org/10.1109/12.381950
[10] Efe, K. (1992) The Crossed Cube Architecture for Parallel Computing. IEEE Transactions on Parallel and Distributed Systems, 3, 513-524.
https://doi.org/10.1109/71.159036
[11] Bhuyan, L.N. and Agrawal, D.P. (1984) Generalized Hypercube and Hyperbus Structures for a Computer Network. IEEE Transactions on Computers, 33, 323-333.
https://doi.org/10.1109/TC.1984.1676437
[12] 师海忠. 互连网络的新模型: 多部群论模型[J]. 计算机科学, 2013, 40(9): 21-24.
[13] 师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学, 2013, 40(6A): 265-270.
[14] 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]//中国运筹学会. 中国运筹学会第十届学术交流会论文集. 香港: Global-Link Informatics Limited, 2010: 202-208.
[15] Shi, H. 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
[16] Haynes, T.W., Hedetniemi, S.T. and Slater P.J.B. (1998) Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York.
[17] Lakshmivarahan, S., Jwo, J.S. and Dhall, S.K. (1993) Symmetry in Interconnection Networks Based on Cayley Graphs of Permutation Groups: A Survey. Parallel Computing, 19, 361-407.
[18] 徐保根. 图的控制理论[M]. 北京: 科学出版社, 2008.
[19] Arumugam, S. and Kala, R. (1998) Domination Parameters of Hypercubes. Journal of the Indian Math, 65, 31-38.
[20] Cohen, G., Honkal, I., Litsym, S. and Lobstein, A. (1997) Covering Codes. Elsevier, Amsterdam.