﻿ 广义<i>b</i>-基超立方体网络的控制数

# 广义b-基超立方体网络的控制数Domination Numbers for Generalized Base-b Hypercube Networks

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 5n8. Furthermore, two problems and two conjectures with the problems are proposed.

[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.

Top