关于网络的控制数的几点注记

展开
  • 浙江师范大学 数学与计算机学院, 浙江金华 321004
郝建修, E-mail: sx35@zjnu.cn

收稿日期: 2019-05-13

  网络出版日期: 2023-09-14

Some remarks about dominating number of network

Expand
  • Institute of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua 321004, Zhejiang, China

Received date: 2019-05-13

  Online published: 2023-09-14

摘要

(d, w)-控制数是一个度量共享网络资源的可靠性的重要参数。(1, 1)-控制数就是图论中的经典控制数, (d, w)-控制数是(1, 1)-控制数的一个直接推广。本文给出了计算(1, w)-控制数的一个下界方法和一个上界方法。应用这两个方法, 求出了超立方体的(1, n-1)-控制数和(1, n)-控制数, 求出了4基n立方体的(1, 2n - 1) -控制数和(1, 2n)-控制数, 求出了n维折叠超立方体的(1, n)-控制数。

本文引用格式

郝建修 . 关于网络的控制数的几点注记[J]. 运筹学学报, 2023 , 27(3) : 185 -190 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.016

Abstract

(d, w) -dominating number is an important measuring parameter for the reliability of sharing common source in a network. (1, 1) -dominating number is also known as dominating number which is a classical parameter in graph theory. (d, w) -dominating number is a simple generalization of (1, 1) -dominating number. In this paper we present a lower bound and an upper bound for the calculating of (1, w) -dominating number. Using these two bounds, we find the (1, n - 1)-dominating number and (1, n)-dominating number for hypercube, we find the (1, 2n - 1) -dominating number and (1, 2n)-dominating number for 4-ary n-cube, and the (1, n)-dominating number for n dimensional folded hypercube.

参考文献

1 Xu J M . Combinatorial Network Theory[M]. Beijing: Science Publisher, 2007.
2 Wang S Y , Li Y , Yang Y X . Fault Tolerant Embeddings in Interconnection Networks[M]. Beijing: Science Publisher, 2012.
3 Bondy J A , Murty U S R . Graph Theory with Applications[M]. London: The Macmillan Press Ltd, 1976.
4 Hsieh S Y , Tsai C Y , Chen C A . Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes[J]. IEEE Transactions on Computers, 2013, 62 (7): 1472- 1477.
5 Xie X , Xu J M . (d, w)-dominating numbers of hypercube networks[J]. Journal of Mathematical Study, 2007, 2 (2): 217- 222.
文章导航

/