CSA  >> Vol. 7 No. 9 (September 2017)

    Domination Numbers for Generalized Base-b Hypercube Networks

  • 全文下载: PDF(713KB) HTML   XML   PP.814-819   DOI: 10.12677/CSA.2017.79093  
  • 下载量: 94  浏览量: 128  


师海忠,杨进霞:西北师范大学数学与统计学院,甘肃 兰州

广义b-基超立方体网络NPC问题控制数Generalized Base-b Hypercube Network NPC Problem Domination Number


控制数是刻画容错网络中资源共享可靠性的一个参数。确定网络的控制数是NPC问题。Lakshmivarahan, Dhall提出了著名的互连网络—广义b-基超立方体网络。该文给出了当b=3,n=2,3,4 时广义b-基超立方体网络控制数的具体值,以及当5n8 时控制数的界;进一步提出了两个问题和与该问题相对应的两个猜想。

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 5n8. 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.
[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.
[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.
[6] El-Amawy, A. and Latifi, S. (1991) Properties and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42.
[7] 师海忠. 互连网络的代数环模型[D]: [博士学位论文]: 北京: 中国科学院应用数学研究所, 1998.
[8] Efe, K. (1991) A Variation on the Hypercube with Lower Diameter. IEEE Transactions on Computer, 40, 1312-1316.
[9] Cull, P. and Larson, S.M. (1995) The Mӧbius Cube. IEEE Transactions on Computer, 44, 647-659.
[10] Efe, K. (1992) The Crossed Cube Architecture for Parallel Computing. IEEE Transactions on Parallel and Distributed Systems, 3, 513-524.
[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.
[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.