Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs

被引：50
作者：
Kikuchi, Yosuke [1 ]
Araki, Toru
机构：
[1] Tsuyama Natl Coll Technol, Dept Elect & Comp Engn, Okayama 7088509, Japan
[2] Iwate Univ, Dept Comp & Informat Sci, Morioka, Iwate 0208551, Japan
来源：
INFORMATION PROCESSING LETTERS | 2006年 / 100卷 / 02期
关键词：
interconnection networks; bubble-sort graph; pancyclicity; edge-pancyclicity;
D O I：
10.1016/j.ipl.2006.05.012
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A bipartite graph G is bipancyclic if G has a cycle of length 1 for every even 4 <= 1 <= vertical bar V (G) vertical bar. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length I of G. In this paper, we show that the bubble-sort graph B-n is bipancyclic for n >= 4 and also show that it is edge-bipancyclic for n >= 5. Assume that F is a subset of E (B-n). We prove that B-n - F is bipancyclic, when n >= 4 and vertical bar F vertical bar <= n -3. Since B-n is a (n-1)-regular graph, this result is optimal in the worst case. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：52 / 59
页数：8
相关论文
共 23 条
[1]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[2]  
ARAGNO E, 2003, RIV MAT U PARMA, V7, P23
[3]  
Araki T, 2003, INFORM PROCESS LETT, V88, P287, DOI 10.1016/j.ip1.2003.09.003
[4]   Pancyclicity of recursive circulant graphs [J].
Araki, T ;
Shibata, Y .
INFORMATION PROCESSING LETTERS, 2002, 81 (04) :187-190
[5]  
Bondy J.A., 1971, J COMBINATORIAL THEO, V11, P80
[6]   EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS [J].
DAY, K ;
TRIPATHI, A .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (08) :1002-1006
[7]   Node-pancyclicity and edge-pancyclicity of crossed cubes [J].
Fan, JX ;
Lin, XL ;
Jia, XH .
INFORMATION PROCESSING LETTERS, 2005, 93 (03) :133-138
[8]   Hamilton-connectivity and cycle-embedding of the Mobius cubes [J].
Fan, JX .
INFORMATION PROCESSING LETTERS, 2002, 82 (02) :113-117
[9]   Cycles in the cube-connected cycles graph [J].
Germa, A ;
Heydemann, MC ;
Sotteau, D .
DISCRETE APPLIED MATHEMATICS, 1998, 83 (1-3) :135-155
[10]   Pancyclicity on Mobius cubes with maximal edge faults [J].
Hsieh, SY ;
Chen, CH .
PARALLEL COMPUTING, 2004, 30 (03) :407-421
123