Premium
Cycle embedding in faulty wrapped butterfly graphs
Author(s) -
Tsai ChangHsiung,
Liang Tyne,
Hsu LihHsing,
Lin MenYang
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10083
Subject(s) - combinatorics , bipartite graph , embedding , vertex (graph theory) , mathematics , graph , enhanced data rates for gsm evolution , discrete mathematics , computer science , telecommunications , artificial intelligence
In this paper, we study the maximal length of cycle embedding in a faulty wrapped butterfly graph BF n with at most two faults in vertices and/or edges. When there is one vertex fault and one edge fault, we prove that the maximum cycle length is n 2 n − 2 if n is even and n 2 n − 1 if n is odd. When there are two faulty vertices, the maximum cycle length is n 2 n − 2 for odd n . All these results are optimal because the wrapped butterfly graph is bipartite if and only if n is even. © 2003 Wiley Periodicals, Inc.