摘要(英) |
In the design of interconnection networks, reliability and efficiency are important
criteria. Recently, the w-wide diameter dw(G), the (w − 1)-fault diameter
Dw(G), and the w-Rabin number rw(G) have been used to measure network reliability
and efficiency. In this thesis, we study these parameters using the strong
w-Rabin number r*w (G). We show that r*k1+k2(G×H) is less than or equal to
max{r*k1(G)+r*k2(H), d(G)+2, d(H) + 2}, where k1 = k(G) and k2 = k(H). |
參考文獻 |
[1] W. S. Chiue, B. S. Shieh, On connectivity of the Cartesian product of two graphs,
Applied Mathematics and Computation 102 (1999) 129-137.
[2] D. F. Hsu, On container width and length in graphs, groups, and networks, IEICE
Transaction on Fundamentals of Electronics, Communications and Computer
Science E77-A (1994) 668-680.
[3] M. S. Krishnamoorthy, B. Krishnamurthy, Fault diameter of interconnection
networks, Computers and Mathematics with Appllications 13 (1987) 577-582.
[4] S. C. Liaw, F. Cao, G. J. Chang, D. F. Hsu, Fault-tolerant routing in circulant
networks and cycle prefix networks, Annals of Combinatorics Vol. 2 (1998).
[5] S. C. Liaw, G. J. Chang, Generalized diameters and Rabin numbers of networks,
J. Combinatorial Optimization 2 (1999) 371-384.
[6] S. C. Liaw, G. J. Chang, Wide diameters of butterfly networks, Taiwanses J. of
Mathematics Vol. 3 No. 1 (1999) 83-88.
[7] S. C. Liaw, G. J. Chang, Rabin numbers of butterfly networks, Discrete Mathematics
196 (1999) 219-227.
[8] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 96-115.
[9] M. O. Rabin, Efficient dispersal of information for security, load balancing, and
fault tolerance, J. Association for Computing Machinery 36 (1989) 335-348.
[10] J. M. Xu, C. Yang, Connectivity of Cartesian product graphs, Discrete Mathematics
306 (2006) 159-165. |