Conditional edge-fault hamiltonicity of matching composition networks

Sun Yuan Hsieh, Chia Wei Lee

研究成果: Article同行評審

56 引文 斯高帕斯(Scopus)


A graph G is called Hamiltonian if there is a Hamiltonian cycle in G. The conditional edge-fault Hamiltonicity of a Hamiltonian graph G is the largest k such that after removing k faulty edges from G, provided that each node is incident to at least two fault-free edges, the resulting graph contains a Hamiltonian cycle. In this paper, we sketch common properties of a class of networks, called Matching Composition Networks (MCNs), such that the conditional edge-fault Hamiltonicity of MCNs can be determined from the found properties. We then apply our technical theorems to determine conditional edge-fault Hamiltonicities of several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, and n-dimensional hyper Petersen networks. Moreover, we also demonstrate that our technical theorems can be applied to network construction.

頁(從 - 到)581-592
期刊IEEE Transactions on Parallel and Distributed Systems
出版狀態Published - 2009 二月 10

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

指紋 深入研究「Conditional edge-fault hamiltonicity of matching composition networks」主題。共同形成了獨特的指紋。