Some problems on Cayley graphs

被引：25

作者：

Konstantinova, Elena ^{[1
]}

机构：

[1] Russian Acad Sci, Siberian Branch, Sobolev Inst Math, Novosibirsk, Russia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2008年 / 429卷 / 11-12期

基金：

俄罗斯基础研究基金会;

关键词：

Cayley graphs; Hamiltonicity problem; Diameter problem; Pancake problems; Sorting by reversals; Vertex reconstruction problem;

D O I：

10.1016/j.laa.2008.05.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This survey paper presents the historical development of some problems on Cayley graphs which are interesting to graph and group theorists such as Hamiltonicity or diameter problems, to computer scientists and molecular biologists such as pancake problem or sorting by reversals, to coding theorists such as the vertex reconstruction problem related to error-correcting codes but not related to Ulam's problem. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：2754 / 2769

页数：16

共 66 条

[1]

Alspach Brian, 1990, CYCLES RAYS, P9

[2] ON THE DIAMETER AND BISECTOR SIZE OF CAYLEY-GRAPHS [J].

ANNEXSTEIN, F ;

BAUMSLAG, M .

MATHEMATICAL SYSTEMS THEORY, 1993, 26 (03) :271-291

[3] ON THE DIAMETER OF CAYLEY-GRAPHS OF THE SYMMETRIC GROUP [J].

BABAI, L ;

SERESS, A .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1988, 49 (01) :175-179

[4] SMALL-DIAMETER CAYLEY-GRAPHS FOR FINITE SIMPLE-GROUPS [J].

BABAI, L ;

KANTOR, WM ;

LUBOTSKY, A .

EUROPEAN JOURNAL OF COMBINATORICS, 1989, 10 (06) :507-522

[5]

BABAI L, 1996, HDB COMBINATORICS, P1447

[6] A linear-time algorithm for computing inversion distance between signed permutations with an experimental study [J].

Bader, DA ;

Moret, BME ;

Yan, M .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2001, 8 (05) :483-491

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

BARTH, D ;

RASPAUD, A .

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

[8]

Bjorner A., 2005, Combinatorics of Coxeter Groups

[9]

Brouwer A.E., 1989, DISTANCE REGULAR GRA

[10]

BRUALDI RA, IPM B

← 1 2 3 4 5 6 7 →