Two edge-disjoint hamiltonian cycles in the butterfly graph
type: Item
instance of: scholarly article
title: Two edge-disjoint hamiltonian cycles in the butterfly graph
zbMATH Open document ID: 0807.05047
DOI: 10.1016/0020-0190(94)00087-5
published in: Information Processing Letters
publication date: 1994-09-25T00:00:00Z
review text: A graph is called a butterfly graph of dimension \(n\) if it is the set of couples \((a; x_{n-1}\ldots x_ 0)\), where \(a\in \{0,\dots,n- 1\}\) and \(x_ i\in \{0,1\}\) for all \(i\in \{0,\dots,n- 1\}\), and \([(a;x_{n- 1}\ldots x_ 0)\), \((a';x_{n-1}'\ldots x_ 0')]\) is an edge of the graph if \(a'\equiv a+1\pmod n\) and if \(x_ i= x_ i'\) for all \(i\neq a'\). The paper shows that the butterfly graph contains two edge-disjoint hamiltonian cycles. It also gives a recursive method for constructing these cycles.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 643656
zbMATH Keywords: butterfly graph
zbMATH Keywords: hamiltonian cycles
author: D. Barth
author: André Raspaud
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00087-5
OpenAlex ID: W1966151552
cites work: Group Action Graphs and Parallel Architectures
cites work: Q3941433
cites work: Hamiltonian decomposition of Cayley graphs of degree 4
cites work: Methods and problems of communication in usual networks
cites work: Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
cites work: Q4002466
cites work: On Hamiltonian cycles in Cayley graphs of wreath products
Recommended article: Two edge-disjoint Hamiltonian cycles in graphs
Recommended article: Two edge-disjoint Hamiltonian cycles of powers of a graph
Recommended article: Q4282956
Recommended article: Edge disjoint Hamilton cycles in graphs
Recommended article: Edge-disjoint Hamilton cycles in graphs
Recommended article: Q4294607
Recommended article: Disjoint Hamiltonian cycles in bipartite graphs
Recommended article: Hamilton cycles and paths in butterfly graphs
Recommended article: Q3701452
Recommended article: Edge-disjoint Hamiltonian cycles in two-dimensional torus
description: scientific article; zbMATH DE number 643656