𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamilton cycles and paths in butterfly graphs

✍ Scribed by Stephen A. Wong

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
536 KB
Volume
26
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

Cycles in butterfly graphs
Cycles in butterfly graphs
✍ Hwang, Shien-Ching; Chen, Gen-Huey 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 3 views

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

Hamilton cycles in regular graphs
Hamilton cycles in regular graphs
✍ Bill Jackson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## UNIVERSIW OF WATERLOO ' The research reported here has been sponsored by the Canadian Commonwealth Association.

Hamilton cycle and Hamilton path extenda
Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
✍ Štefko MiklaviČ; Primož Šparl 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is __n__‐__HC‐extendable__ if it contains a path of length __n__ and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is __weakly n__‐__HP‐

Long paths and cycles in oriented graphs
Long paths and cycles in oriented graphs
✍ Bill Jackson 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 501 KB

## Abstract We obtain several sufficient conditions on the degrees of an oriented graph for the existence of long paths and cycles. As corollaries of our results we deduce that a regular tournament contains an edge‐disjoint Hamilton cycle and path, and that a regular bipartite tournament is hamilto