Hamiltonian connectivity of 2-tree-generated networks

被引：7

作者：

Cheng, Eddie ^{[1
]}

Lipman, Marc J. ^{[2
]}

Liptak, Laszlo ^{[1
]}

Stiebel, David ^{[3
]}

机构：

[1] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA

[2] Indiana Univ Purdue Univ, Sch Arts & Sci, Ft Wayne, IN 46805 USA

[3] MIT, Cambridge, MA 02139 USA

来源：

MATHEMATICAL AND COMPUTER MODELLING | 2008年 / 48卷 / 5-6期

关键词：

interconnection network; Cayley graph; alternating group graph; Hamiltonian connectivity;

D O I：

10.1016/j.mcm.2007.11.007

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we consider a class of Cayley graphs that are generated by certain 3-cycles on the alternating group An. These graphs are generalizations of the alternating group graph AG(n). We look at the case when the 3-cycles form a "tree- like structure", and analyze the Hamiltonian connectivity of such graphs. We prove that even with 2n - 7 vertices deleted, the remaining graph is Hamiltonian connected, i.e. there is a Hamiltonian path between every pair of vertices. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：787 / 804

页数：18

共 17 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2] Hyper hamiltonian laceability of Cayley graphs generated by transpositions [J].

Araki, Toru .

NETWORKS, 2006, 48 (03) :121-124

[3]

Beineke L.W., 1969, J COMB THEORY, V6, P200

[4] PROPERTIES AND CHARACTERIZATIONS OF K-TREES [J].

BEINEKE, LW ;

PIPPERT, RE .

MATHEMATIKA, 1971, 18 (35) :141-&

[5]

Cheng E, 2001, ARS COMBINATORIA, V59, P107

[6] THE (N,K)-STAR GRAPH - A GENERALIZED STAR GRAPH [J].

CHIANG, WK ;

CHEN, RJ .

INFORMATION PROCESSING LETTERS, 1995, 56 (05) :259-264

[7] ARRANGEMENT GRAPHS - A CLASS OF GENERALIZED STAR GRAPHS [J].

DAY, K ;

TRIPATHI, A .

INFORMATION PROCESSING LETTERS, 1992, 42 (05) :235-241

[8] Fault-free Hamiltonian cycles in faulty arrangement graphs [J].

Hsieh, SY ;

Chen, GH ;

Ho, CW .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) :223-237

[9] Fault hamiltonicity of augmented cubes [J].

Hsu, HC ;

Chiang, LC ;

Tan, JJM ;

Hsu, LH .

PARALLEL COMPUTING, 2005, 31 (01) :131-145

[10] Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs [J].

Hsu, HC ;

Li, TK ;

Tan, JJM ;

Hsu, LH .

IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (01) :39-53

← 1 2 →