Search

In the past few years, much importance and attention have been attached to completely independent spanning trees (CISTs). Many results, such as edge-disjoint Hamilton cycles, traceability, number of spanning trees, structural properties, topological indices, etc. have been obtained on line graphs, and researchers have applied the line graphs of some interconnection networks such as generalized hypercubes, augmented cubes, crossed cubes, etc. into data center networks, such as SWCube, AQLCube, BCDC, etc. At the meanwhile, few results of CISTs are reported on the line graphs. In this paper, we establish the relation of edge-disjoint spanning trees in an interconnection network |$G$| ' with its line graph |$G$| by proposing a general algorithm for the first time. By this method, more CISTs can be obtained comparing with results in the literature. Then, the decrease of diameter is discussed and simulation experiments are shown on the line graphs of hypercubes. [ABSTRACT FROM AUTHOR]

Dragonfly networks have been widely used in the current High Performance Computing (HPC) computers due to lower global network diameter and other advantages of communication performance such as modularity and cost-effectiveness. The original definition of the dragonfly network was very loose on account of its uncertain and diversified global link arrangements. In this paper, we study the logical structure of the dragonfly network which can be treated as a compound graph of complete graphs. Firstly, we give the general definition of the dragonfly network, named D F (n , h , g) , and the specific definition of the dragonfly network under the relative global link arrangement, named D (n , h). Then, we prove that the connectivity of D (n , h) is n − 1 + h. In the end, we propose an O (n) algorithm to give the disjoint path between any two distinct vertices in D (n , h) and analyze the maximum length of these disjoint paths which is no more than 7. [ABSTRACT FROM AUTHOR]

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 L T 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 (L T Q n ), D n − 1 f (L T Q n) and D n (L T Q n) denote the diameter, the n − 1 fault diameter and the wide diameter of L T Q n , respectively. In this paper, we prove that D n − 1 f (L T Q n) = D n (L T Q n) = D (L T Q n) + 2 if n is an odd integer with n ≥ 7 , D (L T Q n) + 1 ≤ D n − 1 f (L T Q n) ≤ D n (L T Q n) ≤ D (L T Q n) + 2 if n is an even integer with n ≥ 8. [ABSTRACT FROM AUTHOR]

As a generalization of the star graph, the-star graph is one of the most important interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant routing problem of-star graphs under the conditional fault assumption (CFA), where all the neighbours of any fault-free node cannot be faulty simultaneously. We show that, under the CFA, the-star graph can tolerate up tofaulty nodes, and there is a fault-free path of length at most the diameter of the-star graph plus 6 between any two fault-free nodes. [ABSTRACT FROM PUBLISHER]

The alternating group graph, denoted by AG n , is one of the popular interconnection networks, which has many attractive properties. In this paper, we prove that for any two distinct nodes μ and ν , there exist m node-disjoint paths for any integer n ≥ 3 with 1 ≤ m ≤ 2 n − 4 whose union covers all the nodes of AG n . For any node of AG n has exactly 2 n − 4 neighbors, 2 n − 4 is the maximum number of node-disjoint paths can be constructed in AG n . [ABSTRACT FROM AUTHOR]

The hypercube networkQnhas been proved to be one of the most popular interconnection networks. Then-dimensional locally twisted cube LTQnis an important variant ofQn. One of the critical performance factors of an interconnection network is the diameter which determines the maximum communication time between any pair of processors. In this paper, we investigate the diameter variability problems arising from the addition and deletion of edges in LTQn. We obtain three results in this paper: (1) for any integern≥2, we find the least number of edges (denoted bych−(LTQn)), whose deletion from LTQncauses the diameter to increase, (2) for any integern≥2, whench−(LTQn) edges are deleted, the diameter will increase by 1 and (3) for any integern≥4, the least number of edges whose addition to LTQnwill decrease the diameter is at most 2n−1. [ABSTRACT FROM PUBLISHER]

The crossed cube is an important variant of the hypercube. The n-dimensional crossed cube has only about half diameter, wide diameter, and fault diameter of those of the n-dimensional hypercube. Embeddings of trees, cycles, shortest paths, and Hamiltonian paths in crossed cubes have been studied in literature. Little work has been done on the embedding of paths except shortest paths, and Hamiltonian paths in crossed cubes. In this paper, we study optimal embedding of paths of different lengths between any two nodes in crossed cubes. We prove that paths of all lengths between ... + 1 and 2n - 1 can be embedded between any two distinct nodes with a dilation of 1 in the n-dimensional crossed cube. The embedding of paths is optimal in the sense that the dilation of the embedding is 1. We also prove that ... + 1 is the shortest possible length that can be embedded between arbitrary two distinct nodes with dilation 1 in the n-dimensional crossed cube. [ABSTRACT FROM AUTHOR]

The k -ary n -cube is one of the most attractive interconnection networks for parallel and distributed computing system. In this paper, we investigate hamiltonian cycle and path embeddings in 3-ary n -cubes Q n 3 based on K 1 , 3 -structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K 1 , 3 . We show that for two arbitrary distinct healthy nodes of a faulty Q n 3 , there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most n − 2 and each faulty element is isomorphic to any connected subgraph of K 1 , 3 . We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most n − 1 and each faulty element is isomorphic to any connected subgraph of K 1 , 3 . Then, we provide the simulation experiment to find a hamiltonian cycle and a hamiltonian path in structure faulty 3-ary n -cubes and verify the theoretical results. These results mean that the 3-ary n -cube Q n 3 can tolerate up to 4 ( n − 2 ) faulty nodes such that Q n 3 − V ( F ) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Q n 3 . [ABSTRACT FROM AUTHOR]

Interconnection networks are key component of parallel and distributed systems. As the network scale increases, the growing number of link failures becomes inevitable. Therefore, how to enhance the fault tolerance of the network has become a research issue in parallel and distributed systems. Recently, two new metrics based on edge partition in networks have been introduced, called matroidal connectivity and conditional matroidal connectivity. Existing research indicates that they significantly enhance the fault tolerance of alternating group networks and star networks compared to other indicators such as g -component edge connectivity and g -extra edge connectivity. In this work, we consider the matroidal connectivity and conditional matroidal connectivity of the n -dimensional balanced hypercube B H n , a class of networks with vertex transitivity and edge transitivity, and theoretically demonstrate their high fault tolerance in B H n. Furthermore, through numerical simulation, it is observed that the matroidal connectivity and conditional matroidal connectivity of B H n are greater than the g -component edge connectivity and g -extra edge connectivity of B H n , which implies that (conditional) matroidal connectivity can further improve B H n ' fault tolerance. [ABSTRACT FROM AUTHOR]