Pancyclicity of OTIS (swapped) networks based on properties of the factor graph

• Published in: Information processing letters 2011-12, Vol.111 (23), p.1114-1119
• Main Authors: Malekimajd, M., Hoseiny-Farahabady, M.R., Movaghar, A., Sarbazi-azad, H.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Circuits; Clusters; Computation; Computer networks; Computer science; control theory; systems; Data processing. List processing. Character string processing; Exact sciences and technology; Graph algorithms; Graph theory; Graphs; Hamiltonian cycle; Information retrieval. Graph; Interconnection; Memory organisation. Data processing; Miscellaneous; Modularity; Networks; OTIS (swapped) networks; Pancyclicity; Parallel processing; Quantum physics; Regularity; Software; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2011.07.020

The plausibility of embedding cycles of different lengths in the graphs of a network (known as the pancyclicity property) has important applications in interconnection networks, parallel processing systems, and the implementation of a number of either computational or graph problems such as those used for finding storage schemes of logical data structures, layout of circuits in VLSI, etc. In this paper, we present the sufficient condition of the pancyclicity property of OTIS networks. The OTIS network (also referred to as two-level swapped network) is composed of n clones of an n-node original network constituting its clusters. It has received much attention due to its many favorable properties such as high degree of scalability, regularity, modularity, package-ability and high degree of algorithmic efficiency. Many properties of OTIS networks have been studied in the literature. In this work, we show that the OTIS networks have the pancyclicity property when the factor graph is Hamiltonian. More precisely, using a constructive method, we prove that if the factor graph G of an OTIS network contains cycles of length { 3 , 4 , 5 , l } , then all cycles of length { 3 , … , l 2 } , can be embedded in the OTIS - G network. This result resolves the open question posed and tracked in Day and AlAyyoub (2002) [2], Hoseiny Farahabady and Sarbazi Azad (2007) [4] and Shafiei et al. (2011) [14]. ► OTIS- G has all cycles of length 7 to l 2 if the factor graph G contains an l- cycle. ► We present schema to build any cycle in OTIS - G when graph G is Hamiltonian. ► OTIS - G is pancyclic if the factor graph G contains cycles of length { 3 , 4 , 5 , | V ( g ) | } .