Premium
Hamilton cycles and paths in butterfly graphs
Author(s) -
Wong Stephen A.
Publication year - 1995
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.3230260304
Subject(s) - combinatorics , hamiltonian path , vertex (graph theory) , mathematics , bipartite graph , graph , path (computing) , complete graph , discrete mathematics , computer science , programming language
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 .