Disjoint Hamiltonian cycles in recursive circulant graphs

被引：21

作者：

Micheneau, C

机构：

[1] LaBRI, URA CNRS 1304, Université Bordeaux I, 351, cours de la Libération, 33405 Talence Cedex, France

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 61卷 / 05期

关键词：

combinatorial problems; Cayley graph; circulant graph; Hamiltonian decomposition;

D O I：

10.1016/S0020-0190(97)00020-3

中图分类号：

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

学科分类号：

0812 ;

摘要：

We show in this paper that the circulant graph G(2(m), 4) is Hamiltonian decomposable, and propose a recursive construction method. This is a partial answer to a problem posed by B. Alspach. (C) 1997 Published by Elsevier Science B.V.

引用

页码：259 / 264

页数：6

共 8 条

[1]

ALSPACH B, 1984, DISCRETE MATH, V50, P115

[2] 2 EDGE-DISJOINT HAMILTONIAN CYCLES IN THE BUTTERFLY GRAPH [J].

BARTH, D ;

RASPAUD, A .

INFORMATION PROCESSING LETTERS, 1994, 51 (04) :175-179

[3]

Berge C, 1976, Graphs and Hypergraphs

[4] 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

[5]

CURRAN SJ, 1994, HAMILTONIAN CYCLES P

[6]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architecture: Arrays. Trees. Hypercubes

[7] HAMILTONIAN DECOMPOSITIONS OF CAYLEY-GRAPHS ON ABELIAN-GROUPS [J].

LIU, JQ .

DISCRETE MATHEMATICS, 1994, 131 (1-3) :163-171

[8]

Park J. H., 1994, P INT S PAR ARCH ALG, P73, DOI DOI 10.1109/ISPAN.1994.367162

← 1 →