Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements
In this paper, we deal with the graph G(0) circle plus G(1) obtained from merging two graphs G(0) and G(1) with n vertices each by n pairwise nonadjacent edges joining vertices in G(0) and vertices in G(1). The main problems studied are how fault-panconnectivity and fault-pancyclicity of G(0) and G(1) are translated into fault-panconnectivity and fault-pancyclicity of Go e G 1, respectively. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G(0) circle plus G(1) connecting two lower dimensional networks G(0) and G(1). Applying our results to a class of hypercube-like interconnection networks called restricted HL-graphs, we show that in a restricted HL-graph G of degree m (>= 3), each pair of vertices are joined by a path in G\F of every length from 2m - 3 to vertical bar V (G\ F)vertical bar-1 for any set F of faulty elements (vertices and/or edges) with vertical bar F vertical bar <= m(-3), and there exists a cycle of every length from 4 to vertical bar V (G\F)vertical bar for any fault set F with vertical bar F vertical bar <= m(-2). (c) 2007 Elsevier B.V All rights reserved.
panconnected pancyclic interconnection networks restricted hl-graphs embedding edge-pancyclic fault-hamiltonicity fault tolerance