2 EDGE-DISJOINT HAMILTONIAN CYCLES IN THE BUTTERFLY GRAPH

被引：32

作者：

BARTH, D ^{[1
]}

RASPAUD, A ^{[1
]}

机构：

[1] UNIV BORDEAUX 1,LABRI,CNRS,URA 1304,F-33405 TALENCE,FRANCE

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 51卷 / 04期

关键词：

COMBINATORIAL PROBLEMS; COMPUTER ARCHITECTURE; BUTTERFLY GRAPH; CAYLEY GRAPHS; HAMILTONIAN CYCLES;

D O I：

10.1016/0020-0190(94)00087-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that the butterfly graph contains two edge-disjoint hamiltonian cycles by giving a recursive method of construction of this cycles. This solves a conjecture proposed by D. Sotteau and J. Rowley.

引用

页码：175 / 179

页数：5

共 11 条

[1]

Alspach B., 1985, ANN DISCRETE MATH, V27, P464

[2]

AMESTOY PR, 1992, LECTURE NOTES COMPUT, P319

[3] GROUP ACTION GRAPHS AND PARALLEL ARCHITECTURES [J].

ANNEXSTEIN, F ;

BAUMSLAG, M ;

ROSENBERG, AL .

SIAM JOURNAL ON COMPUTING, 1990, 19 (03) :544-569

[4]

Berge C., 1976, GRAPHS HYPERGRAPHS

[5] HAMILTONIAN DECOMPOSITION OF CAYLEY-GRAPHS OF DEGREE-4 [J].

BERMOND, JC ;

FAVARON, O ;

MAHEO, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :142-153

[6]

DERUMEUR J, 1993, IN PRESS COMMUNICATI

[7]

FRAIGNIAUD P, 1991, LRI701 U PARIS SUD C

[8]

LAKSHMIVARAHAN S, 1991, ANAL SYMMETRY INTERC

[9]

Leighton FT., 1992, INTRO PARALLEL ALGOR

[10]

SOTTEAU D, 1992, COMMUNICATION

← 1 2 →