Two problems on butterfly graphs
Resource
Parallel and Distributed Systems, 1998. Proceedings., 1998 International Conference on
Journal
1998 International Conference on Parallel and Distributed Systems
Pages
-
Date Issued
1998-12
Date
1998-12
Author(s)
Hwang, Shien-Ching
DOI
N/A
Abstract
The cycle partition problem and the pancycle problem on butterfly graphs are studied in this paper. Suppose G=(V,E) is a graph and {V/sub 1/,V/sub 2/,...,V/sub s/} is a partition of V. We say that {V/sub 1/,V/sub 2/,...,V/sub s/} forms a cycle partition of G if each subgraph of G induced by V/sub 1/ contains a cycle of length |V/sub i/|, where 1/spl les/i/spl les/s. A cycle partition {V/sub 1/,V/sub 2/,...,V/sub s/} is /spl lambda/-uniform if |V/sub 1/|=|V/sub 2/|=...=|V/sub s/|=/spl lambda/. G has /spl lambda/-complete uniform cycle partitions if G has m/spl lambda/-uniform cycle partitions for all 1/spl les/m/spl les/(r+n)/2 and m dividing |V|//spl lambda/. Let BF(k,r) denote the r-dimensional k-ary butterfly graph. For the cycle partition problem, we construct a lot of uniform cycle partitions for BF(k,r). Besides, we construct r-complete uniform cycle partitions for BF(2,r), and kr-complete uniform cycle partitions for BF(k,r). For the pancycle problem, given any pair of n and r we can determine if there exists a cycle of length n in BF(2,r), and construct it if it exists. The results of this paper reveal that the butterfly graphs are superior in embedding rings. They can embed rings of almost all possible lengths. Besides, there are many situations in which they can embed the most rings of the same length.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00741134.pdf
Size
749.72 KB
Format
Adobe PDF
Checksum
(MD5):0a2262d87c69d56a263cd3afc08d81e8