Hamilton cycles and paths in butterfly graphs

A cycle C in a graph G is a Hamilton cycle if C contains every vertex of G . Similarly, a path P in G is a Hamilton path if P contains every vertex of G . We say that G is Hamilton ‐ connected if for any pair of vertices, u and v of G , There exists a Hamilton path from u to v . If G is a bipartite graph with bipartition sets of equal size, and there is a Hamilton path from any vertex in one bipartition set to any vertex in the other, The n G is said to be Hamilton ‐ laceable . We present a proof showing that the n ‐dimensional k ‐ary butterfly graph, denoted BF(k, n ), contains a Hamilton cycle. Then, we use this result in proving the stronger result that BF (k, n ) is Hamilton‐laceable when n is even and Hamilton‐connected for odd values of n .