Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes |
| |
Authors: | Tseng-Kuei Li Chang-Hsiung Tsai Lih-Hsing Hsu |
| |
Affiliation: | a Department of Computer Science and Information Engineering, Ching Yun Institute of Technology JungLi 320, Taiwan, R.O.C. b Department of Computer and Information Science, National Chiao Tung University, Hsinchu 30050, Taiwan, R.O.C. |
| |
Abstract: | A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Qn is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Qn−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Qn) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Qn when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y. |
| |
Keywords: | Hypercube Hamiltonian Bipancyclic Bipanconnected Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|