Edge-bipancyclicity of star graphs with faulty elements |
| |
Authors: | Chao-Wen Huang |
| |
Affiliation: | a National Center for High-Performance Computing (Taichung Branch), No. 22, Keyuan Rd., Central Taiwan Science Park, Taichung 40763, Taiwanb Department of Information Management, Southern Taiwan University, No. 1, Nantai St, Yung-Kang City, Tainan 710, Taiwanc Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 701, Taiwan |
| |
Abstract: | In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph Sn. Given a set F comprised of faulty vertices and/or edges in Sn with |F|≤n−3 and any fault-free edge e in Sn−F, we show that there exist cycles of every even length from 6 to n!−2|Fv| in Sn−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite Sn is n!−2|Fv| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|Fv|+2 to n!−2|Fv| can be embedded. |
| |
Keywords: | Cayley graphs Edge-bipancyclicity Fault-tolerant embedding Interconnection networks Star graphs |
本文献已被 ScienceDirect 等数据库收录! |
|