Bipancyclic properties of Cayley graphs generated by transpositions

被引：14

作者：

Tanaka, Yuuki ^{[1
]}

Kikuchi, Yosuke ^{[2
]}

Araki, Toru ^{[3
]}

Shibata, Yukio ^{[3
]}

机构：

[1] Kyushu Inst Technol, Informat Sci Ctr, Fukuoka 8048550, Japan

[2] Tsuyama Natl Coll Technol, Dept Comp & Informat Engn, Okayama 7088509, Japan

[3] Gunma Univ, Grad Sch Engn, Dept Comp Sci, Gunma 3768515, Japan

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 04期

关键词：

Cayley graph; Bipancyclicity; Transposition tree; CYCLES;

D O I：

10.1016/j.disc.2009.09.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Cycle is one of the most fundamental graph classes. For a given graph, it is interesting to find cycles of various lengths as subgraphs in the graph. The Cayley graph Cay(e., S) on the symmetric group has an important role for the study of Cayley graphs as interconnection networks. In this paper, we show that the Cayley graph generated by a transposition set is vertex-bipancyclic if and only if it is not the star graph. We also provide a necessary and sufficient condition for Cay(n, S) to be edge-bipancyclic. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：748 / 754

页数：7

共 17 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

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

Araki, Toru .

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

[3] Linearly many faults in Cayley graphs generated by transposition trees [J].

Cheng, Eddie ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2007, 177 (22) :4877-4882

[4] NEW METHODS FOR USING CAYLEY-GRAPHS IN INTERCONNECTION NETWORKS [J].

COOPERMAN, G ;

FINKELSTEIN, L .

DISCRETE APPLIED MATHEMATICS, 1992, 37-8 :95-118

[5] EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS [J].

DAY, K ;

TRIPATHI, A .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (08) :1002-1006

[6]

Delorme C., 1997, Isomorphism of Transposition Graphs

[7] Cycles in the cube-connected cycles graph [J].

Germa, A ;

Heydemann, MC ;

Sotteau, D .

DISCRETE APPLIED MATHEMATICS, 1998, 83 (1-3) :135-155

[8]

Godsil C., 2001, Algebraic graph theory

[9]

Heydemann MC, 1997, NATO ADV SCI I C-MAT, V497, P167

[10]

Hwang SC, 2000, NETWORKS, V35, P161, DOI 10.1002/(SICI)1097-0037(200003)35:2<161::AID-NET7>3.0.CO

← 1 2 →