Abstract A graph $G=(V,E)$ is two-disjoint-cycle-cover $[r_1,r_2]$-pancyclic if for any integer $l$ satisfying $r_1 \leq l \leq r_2$, there exist two vertex-disjoint cycles $C_1$ and $C_2$ in $G$ such that the lengths of $C_1$ and $C_2$ are $l$ and $|V(G)| - l$, respectively, where $|V(G)|$ denotes the total number of vertices in $G$. On the basis of this definition, we further propose Ore-type conditions for graphs to be two-disjoint-cycle-cover vertex/edge $[r_1,r_2]$-pancyclic. In addition, we study cycle embedding in the $n$-dimensional locally twisted cube $LTQ_n$ under the consideration of two-disjoint-cycle-cover vertex/edge pancyclicity.

We propose two new measures of conditional connectivity to be the extension of R g -connectivity and R g -edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional ( g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg G–F ( p) + deg G–F ( q) ≥ 2 g + k for every two distinct vertices p and q in G – F with d( p, q) ≤ d. The ( g, d, k)-conditional(-edge)-connectivity, denoted by κ g,d,k ( λ g,d,k ), is the minimum cardinality of a conditional ( g, d, k)(-edge)-cut. Based on these requirements, we obtain κ 1,1, k , κ 1, d,2 , λ 1,1,1 and λ 1, d,2 for the hypercubes.

Interconnection networks are evolving as a universal approach to solving system-level communication problems in real-world applications. An interconnection network is a programmable system that serves to transport data or messages between components/terminals in a network system. Hypercube is one of the most widely studied network structures for inter-connecting a huge number of network components so that it has long been considered as a good candidate for network architectures. Unidirectional hypercube are obtained from hypercubes by orienting the direction of each edge in a well-defined manner. As routing plays an important role in achieving almost all aspects of network functionalities, this paper makes a theoretical analysis on the channel congestion of the dimension-ordered shortest-path-algorithm with respect to unidirectional hypercubes.

A graph G is pancyclic if it contains a cycle C of every length with 3≤l(C)≤∣V(G)∣⁠, where l(C) denotes the length of C and ∣V(G)∣ denotes the number of vertices in G. In this paper, we propose an augmented pancyclicity problem for the n-dimensional crossed cube CQn, which is a popular variant of the hypercube network. Let dC(u,v) denote the distance between any two distinct vertices u and v traversed by a cycle C in CQn, n≥4⁠. Then, for any integer m with ⌈n+12⌉+1≤m≤2n−1⁠, there exist cycles C of various lengths in CQn such that dC(u,v)=m⁠, where (i) 2m+1≤l(C)≤2n if n is odd and m=⌈n+12⌉+1 and (ii) 2m≤l(C)≤2n otherwise. This result indicates that any two distinct vertices of crossed cubes can be embedded on cycles of various feasible lengths with keeping any feasible distance from each other.

An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t-1)°-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(logN)2) with our algorithm, where N is the total number of the processors in the network.

Abstract The alternating group graph AGn is an interconnection network topology based on the Cayley graph of the alternating group. There are some interesting results concerning the hamiltonicity and the fault tolerant hamiltonicity of the alternating group graphs. In this article, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer l satisfying d(x,y) ≤ l ≤ ∣V(G)∣−d(x,y), there exists a hamiltonian cycle C of G such that the relative distance between x, y on C is l. We show that AGn is panpositionable hamiltonian if n ≥ 3. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 146–156 2007

Abstract Letuandvbe any two distinct nodes of an undirected graphG, which isk‐connected. A containerC(u,v) betweenuandvis a set of internally disjoint paths {P1,P2,…,Pw} betweenuandvwhere 1 ≤w≤k. The width ofC(u,v) iswand the length ofC(u,v) {written aslC(u,v) is max {l(Pi) ∣ 1 ≤i≤w}. Aw‐containerC(u,v) is a container with widthw. Thew‐wide distance betweenuandv,dw(u,v), is min {l(C(u,v)) ∣C(u,v) is aw‐container}. Aw‐containerC(u,v) of the graphGis aw*‐container if every node ofGis incident with a path inC(u,v). That means that thew‐containerC(u,v) spans the whole graph. LetSnbe then‐dimensional star graph withn≥ 5. It is known thatSnis bipartite. In this article, we show that, for any pair of distinct nodesuandvin different partite sets ofSn, there exists an (n− 1)*‐containerC(u,v) and the (n− 1)‐wide distanced(n− 1)(u,v) is less than or equal to${n!\over n-2}+1$ . In addition, we also show the existence of a 2*‐containerC(u,v) and the 2‐wide distanced2(u,v) is bounded above by${n!\over 2}+1$ . © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 235–249 2006

Two hamiltonian paths P1 = 〈u1, u2,…,un(G)〉 and P2 = 〈v1, v2,…,vn(G)〉 of G from u to v are independent if u = u1 = v1, v = vn(G) = un(G), and vi ≠ ui for every 1 < i < n(G). A set of hamiltonian paths, lP1, P2,…,Pkr, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k-mutually independent hamiltonian laceable if there exists k-mutually independent hamiltonian paths between any two nodes from distinct partite sets. The mutually independent hamiltonian laceability of a bipartite graph G, IHPL(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Sn denote the n-dimensional star graph. We prove that IHPL(S2) = 1, IHPL(S3) = 0, and IHPL(Sn) = n- 2 if n ≥ 4. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 110–117 2005

Diagnosability has played an important role in the reliability of an interconnection network. The classical problem of fault diagnosis is discussed widely and the diagnosability of many well-known networks have been explored. We introduce a new measure of diagnosability, called conditional diagnosability, by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional hypercube is shown to be 4(n - 2) +1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable and introduce a new concept, called a strongly t-diagnosable system, under the PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.

Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.

The arrangement graph A/sub n,k/ is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. We improve these results and obtain a stronger and simpler statement. Let n-k/spl ges/2 and F/spl sube/V(A/sub n,k/)/spl cup/E(A/sub n,k/). We prove that A/sub n,k/-F is Hamiltonian if |F|/spl les/k(n-k)-2 and A/sub n,k/-F is Hamiltonian connected if |F|/spl les/k(n-k)-3. These results are optimal.

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks has been explored. We consider the diagnosability of a family of networks, called the matching composition network (MCN); a perfect matching connects two components. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the hypercube Qn, the crossed cube CQ/sub n/, the twisted cube TQ/sub n/, and the Mobius cube MQ/sub n/ can all proven to be n, for n/spl ges/4. In particular, we show that the diagnosability of the four-dimensional hypercube Q/sub 4/ is 4, which is not previously known.

Abstract In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)‐star graph Sn,k. Assume that F ⊂ V(Sn,k) ∪ E(Sn,k). For n − k ≥ 2, we prove that Sn,k − F is Hamiltonian if |F| ≤ n − 3 and Sn,k − F is Hamiltonian connected if |F| ≤ n − 4. For n − k = 1, Sn,n−1 is isomorphic to the n‐star graph Sn which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. © 2003 Wiley Periodicals, Inc.

The star graph is an attractive alternative to the hypercube graph. It possess many nice topological properties. Edge fault tolerance is an important issue for a network since the edges in the network may fail sometimes. In this paper, we show that the n-dimensional star graph is (n-3)-edge fault tolerant hamiltonian laceable, (n-3)-edge fault tolerant strongly Hamiltonian laceable, and (n-4)-edge fault tolerant hyper Hamiltonian laceable. All these results are optimal in a sense described in this paper.

Abstract A graphGis a combinedk‐fault‐tolerant Hamiltonian graph (also called a combinedk‐Hamiltonian graph) ifG−Fis Hamiltonian for every subsetF⊂ (V(G) ∪E(G)) with |F| =k. A combinedk‐Hamiltonian graphGwith |V(G)| =nis optimal if it has the minimum number of edges among alln‐nodek‐Hamiltonian graphs. Using the concept of node expansion, we present a powerful construction scheme to construct a larger combinedk‐Hamiltonian graph from a given smaller graph. Many previous graphs can be constructed by the concept of node expansion. We also show that our construction maintains the optimality property in most cases. The classes of optimal combinedk‐Hamiltonian graphs that we constructed are shown to have a very good diameter. In particular, those optimal combined 1‐Hamiltonian graphs that we constructed have a much smaller diameter than that of those constructed previously by Mukhopadhyaya and Sinha, Harary and Hayes, and Wang et al. © 2001 John Wiley & Sons, Inc.

In this paper, we address the problem of minimizing channel contention of linear-complement communication on wormhole-routed hypercubes. Our research reveals that, for traditional routing algorithms, the degree of channel contention of a linear-complement communication can be quite large. To solve this problem, we propose an alternative approach, which applies processor reordering mapping at compile time. In this compiler approach, processors are logically reordered according to the given communication(s) so that the new communication(s) can be efficiently realized on the hypercube network. It is proved that, for any linear-complement communication, there exists a reordering mapping such that the new communication has minimum channel contention. An O(n/sup 3/) algorithm is proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on dynamic programming is also proposed to find an optimal reordering mapping for a set of linear-complement communications. Several computer simulations have been conducted and the results clearly show the advantage of the proposed approach.

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. © 2000 John Wiley & Sons, Inc.

An n-dimensional crossed cube, CQ/sub n/, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n/sup 2/) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2/sup n-1/. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four.

We show that the cyclic-cubes defined by Ada W.C. Fu and S.C. Chau (1998) are isomorphic to k-ary wrapped butterfly networks.

For distributed memory parallel computers, broadcast operations are widely used in a variety of applications. In this paper we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 2D torus with arbitrary size. The underlying network is assumed to support only the dimension-ordered unicast. By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can greatly reduce the number of message-passing steps. In addition, it can be proved to be depth contention-free. The performance study in this paper clearly shows the advantage of the proposed algorithm.

The token ring topology is required in the token passing approach used in distributed operating systems. Fault tolerance is also required in the design of distributed systems. We consider the 1-fault-tolerant design for token rings, which can tolerate 1-processor fault- or 1-link fault. Note that the 1-fault-tolerant design for token rings is equivalent to the design of 1-Hamiltonian graphs. The paper introduces a new family of interconnection networks called Christmas tree. The under graph of the Christmas tree, denoted by CT(s), is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes and the diameter of CT(s) are 3/spl times/2/sup s/-2 and 2s, respectively. In other words, the diameter of CT(s) is 2 log/sub 2/ n-O(1), where n is the number of nodes.

For distributed memory parallel computers, broadcast operations arc widely used in a variety of applications.In this paper, we propose an eflicicnt algorithm for broadcasting on an all-port wormhole-routed 2D torus.The underlying network is assumed to support only the dimensionordered unicast routing.By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can be proved to be depth contention-free, and needs only n steps for broadcasting on a 2d~2" torus.Furthermore, the software latency is also reduced by appropriately overlaying the messages sent out by the same node in each step.The timing analysis and the computer simulation conducted in this paper clearly show the performance im provement of the proposed algorithm.

Architectures for interconnection networks can be represented by graphs, while vertices represent processors and edges represent communication links between processors. We use the terms vertices and processors interchangeably. Let G = (V, E) be a graph representing the topology for an interconnection network. Let v0 be a special vertex outside G, called the host processor, which is connected to each vertex in G. The host processor is the sender or source of the message to be transmitted to all of the vertices in G. In each time unit, the host processor may send an identical message to an arbitrary vertex in G or remain idle. At the same time, each processor in G that has already received the message can send it to all its neighbors in one time unit. A transmitting scheme allowing all processors to receive the message in t time units and requiring the host processor to send the message s times is called a (t, s)-transmitting scheme, where t ≥ s. We call t the transmitting time, and s, the workload of the host processor. We aimed to find an optimal transmitting scheme, i.e., a transmitting scheme such that t is minimized while s is also minimized. In this paper, we present optimal transmitting schemes for linear arrays, rings, complete binary trees, star trees, and (directed) de Bruijn graphs. Furthermore, we present a (t, s)-transmitting scheme for diagonal meshes which are defined slightly different from meshes, and the ratio of t to the optimal transmitting time is approximate to 1.1. © 1996 John Wiley & Sons, Inc.

Abstract Let G = (V,E) be an undirected graph having an edge weight we ≥ 0 for each e ϵ E. An edge is called a most vital edge (with respect to weighted matching) if its removal from G results in the largest decrease in the total weight of the maximum weighted matching. In this paper, we study the most vital edges of matching in a weighted bipartite graph. We present an O(n3) algorithm to obtain the most vital edges. © 1993 by John Wiley & Sons, Inc.

Abstract A series‐parallel network is used as a model of electric circuits. Usually, we use a series‐parallel graph to represent a series‐parallel network. However, there are a lot of different graph representations for a single series‐parallel network. For a given graph, a subset of V(G) is called an independent set if there are no edge of G joining two vertices in S. An independent set S of G is maximum if G has no independent set S′ with |S′| > |S|. The number of vertices in a maximum independent set of G is called the independent number of G and is denoted by α(G). The maximum independent number α(N) for a series‐parallel network N is defined to be the maximum α(G[N]) among all possible graph representations G[N]. In this paper, we are going to present a linear time algorithm to compute α(N) for any series‐parallel network N.