Wide diameters of de Bruijn graphs |
| |
| Authors: | Jyhmin Kuo Hung-Lin Fu |
| |
| Affiliation: | (1) Department of Applied Mathematics, NCTU, Hsinchu, 300, Taiwan |
| |
| Abstract: | The wide diameter of a graph is an important parameter to measure fault-tolerance of interconnection network. This paper proves that for any two vertices in de Bruijn undirected graph UB(d,n), there are 2d−2 internally disjoint paths of length at most 2n+1. Therefore, the (2d−2)-wide diameter of UB(d,n) is not greater than 2n+1. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday. |
| |
| Keywords: | de Bruijn Internally disjoint path Wide diameter |
| 本文献已被 SpringerLink 等数据库收录！ |
|
