Narrow Results

The topology properties of multi-processors interconnection networks are important to the performance of high performance computers. The hypercube network $Q_n$ has been proved to be one of the most popular interconnection networks. The $n$-dimensional locally twisted cube $LT{Q}_n$ is an important variant of $Q_n$. Fault diameter and wide diameter are two communication performance evaluation parameters of a network. Let $D(LT{Q}_n$), $D_{n-1}^f(LT{Q}_n)$ and $D_n(LT{Q}_n)$ denote the diameter, the $n-1$ fault diameter and the wide diameter of $LT{Q}_n$, respectively. In this paper, we prove that $D_{n-1}^f(LT{Q}_n)=D_n(LT{Q}_n)=D(LT{Q}_n)+2$ if $n$ is an odd integer with $n\ge 7$, $D(LT{Q}_n)+1\le D_{n-1}^f(LT{Q}_n)\le D_n(LT{Q}_n)\le D(LT{Q}_n)+2$ if $n$ is an even integer with $n\ge 8$.

The fault diameter and wide diameter are commonly used to measure the fault tolerance and transmission delay of interconnection networks beyond traditional diameter. The $\alpha$-wide diameter of graph $G$, denoted by $D_{\alpha }(G)$, is the minimum integer $l$ such that there exist at least $\alpha$ internally vertex disjoint paths of length at most $l$ for any two distinct vertices in $G$. The $\beta$-fault diameter of graph $G$, denoted by $D_{\beta }^f(G)$, is the maximum diameter of the survival graph obtained by deleting at most $\beta$ vertices in $G$. The exchanged crossed cube, as a compounded interconnection network denoted by $ECQ(s,t)$, holds the desirable properties of both crossed cube and exchanged hypercube, while achieving a better balanced between cost and performance of the parallel computing systems. In this paper, we construct $s+1$ internally vertex disjoint paths between any two distinct vertices of $ECQ(s,t)$. Moreover, we determine the upper and lower bounds of $(s+1)$-wide diameter and $s$-fault diameter of $ECQ(s,t)$, i.e., $\lceil \frac{s}{2}\rceil +\lceil \frac{t+1}{2}\rceil +4\le D_s^f(ECQ(s,t))\le D_{s+1}(ECQ(s,t))\le \lceil \frac{s+1}{2}\rceil +\lceil \frac{t+1}{2}\rceil +5$, which shows that the exchanged crossed cube has better efficiency and reliability than that of the exchanged hypercube.

The Möbius cube is a variant of the hypercube and has better performance than the hypercube with the same number of links and processors. This paper shows that the wide diameter of the Möbius cube is at most , about one half of the same dimensional hypercube's.

Because of its applications in network theory, the wide diameter of graphs has been studied extensively in recent years. It is still an open problem to compute the wide diameter of Cayley graphs. This paper investigates the wide diameter of Cayley graphs of ℤ_m, the cyclic group of residue classes modulo m. It is proved that the k-wide diameter of the Cayley graph Cay(Z_m, A) generated by a k-element set A is d + 1 for k = 2 and ≤ d + 1 for k = 3, where d is the diameter of Cay(ℤ_m, A).

The w-wide diameter of a graph is a generalisation of its diameter and connectivity, and is useful for measuring the reliability of an interconnection network. The Gaussian networks, which are defined via quotient rings of the Gaussian integers, have been shown to satisfy many good properties of an interconnection network. In this paper, we will establish the wide diameters of the Gaussian networks and show that they are at most three more than the diameter.

In any network, the diameter is often taken as a measure of efficiency, as it measures the maximum communication delay. The fact that addition or deletion of edges changes the diameter gives rise to the concept of diameter variability. Its study becomes important as it determines the communication efficiency when an addition or deletion of a link occurs in a network. Two other important graph parameters considered as a measure of reliability and efficiency of networks are wide diameter and fault diameter. In this paper, we study these diameter notions of the Fibonacci cubes.

The network components of interconnection networks are exposed to failures. But it is necessary that a network should not break down when such failures occur. Thus reliability and efficiency of interconnection networks have been the subject of extensive study in past years. The connectivity, wide diameter, Rabin number, and fault diameter of a network are used as measures of reliability and efficiency. In this paper, the $3$-wide diameter, $3$-Rabin number, and $1$-fault diameter of brother tree BT$(s)$, $s\ge 2$ are obtained.