Premium
Cycles in butterfly graphs
Author(s) -
Hwang ShienChing,
Chen GenHuey
Publication year - 2000
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/(sici)1097-0037(200003)35:2<161::aid-net7>3.0.co;2-q
Subject(s) - combinatorics , partition (number theory) , mathematics , butterfly , embedding , hamiltonian path , chordal graph , discrete mathematics , graph , computer science , finance , artificial intelligence , economics
Abstract Three problems in connection with cycles on the butterfly graphs are studied in this paper. The first problem is to construct complete uniform cycle partitions for the butterfly graphs. Suppose that G = ( V, E ) is a graph. A partition { V 1 , V 2 , …, V s } of V is said to be a uniform cycle partition of G if | V 1 | = | V 2 | = … = | V s | and each subgraph of G induced by V i contains a cycle of length | V i |, where 1 ≤ i ≤ s . We say that G has λ‐complete uniform cycle partitions if G has uniform cycle partitions whose cycle lengths include all possible multiples of λ. The second problem is to determine if there exists a cycle of length n in the butterfly graphs, where n is arbitrarily given. The third problem is to establish Hamiltonian cycles in faulty butterfly graphs. The results of this paper reveal that the butterfly graphs are superior in embedding rings. © 2000 John Wiley & Sons, Inc.